This letter simplifies and analyze existing state evolution recursions for conjugate gradient. The proposed simplification reduces the complexity for solving the recursions from cubic order to square order in the total number of iterations. The simplified recursions are still catastrophically sensitive to numerical errors, so that arbitrary-precision arithmetic is used for accurate evaluation of the recursions.

Magnetic fields are often utilized for position sensing of mobile devices. In typical sensing systems, multiple sensors are used to detect magnetic fields generated by target devices. To determine the positions of the devices, magnetic-field data detected by the sensors must be converted to device-position data. The data conversion is not trivial because it is a nonlinear inverse problem. In this study, we propose a machine-learning approach suitable for data conversion required in the magnetic-field-based position sensing of target devices. In our approach, two different sets of training data are used. One of the training datasets is composed of raw data of magnetic fields to be detected by sensors. The other set is composed of logarithmically represented data of the fields. We can obtain two different predictor functions by learning with these training datasets. Results show that the prediction accuracy of the target position improves when the two different predictor functions are used. Based on our simulation, the error of the target position estimated with the predictor functions is within 10cm in a 2m × 2m × 2m cubic space for 87% of all the cases of the target device states. The computational time required for predicting the positions of the target device is 4ms. As the prediction method is accurate and rapid, it can be utilized for the real-time tracking of moving objects and people.

Convolutional approximate message-passing (CAMP) is an efficient algorithm to solve linear inverse problems. CAMP aims to realize advantages of both approximate message-passing (AMP) and orthogonal/vector AMP. CAMP uses the same low-complexity matched-filter as AMP. To realize the asymptotic Gaussianity of estimation errors for all right-orthogonally invariant matrices, as guaranteed in orthogonal/vector AMP, the Onsager correction in AMP is replaced with a convolution of all preceding messages. CAMP was proved to be asymptotically Bayes-optimal if a state-evolution (SE) recursion converges to a fixed-point (FP) and if the FP is unique. However, no proofs for the convergence were provided. This paper presents a theoretical analysis for the convergence of the SE recursion. Gaussian signaling is assumed to linearize the SE recursion. A condition for the convergence is derived via a necessary and sufficient condition for which the linearized SE recursion has a unique stationary solution. The SE recursion is numerically verified to converge toward the Bayes-optimal solution if and only if the condition is satisfied. CAMP is compared to conjugate gradient (CG) for Gaussian signaling in terms of the convergence properties. CAMP is inferior to CG for matrices with a large condition number while they are comparable to each other for a small condition number. These results imply that CAMP has room for improvement in terms of the convergence properties.

We propose a useful formulation for ill-posed inverse problems in Hilbert spaces with nonlinear clipping effects. Ill-posed inverse problems are often formulated as optimization problems, and nonlinear clipping effects may cause nonconvexity or nondifferentiability of the objective functions in the case of commonly used regularized least squares. To overcome these difficulties, we present a tractable formulation in which the objective function is convex and differentiable with respect to optimization variables, on the basis of the Bregman divergence associated with the primitive function of the clipping function. By using this formulation in combination with the representer theorem, we need only to deal with a finite-dimensional, convex, and differentiable optimization problem, which can be solved by well-established algorithms. We also show two practical examples of inverse problems where our theory can be applied, estimation of band-limited signals and time-harmonic acoustic fields, and evaluate the validity of our theory by numerical simulations.

In 1999, Boneh and Durfee introduced the small inverse problem, which solves the bivariate modular equation x(N+y)≡1(mod e. Absolute values of solutions for x and y are bounded above by X=Nδ and Y=Nβ, respectively. They solved the problem for β=1/2 in the context of small secret exponent attacks on RSA and proposed a polynomial time algorithm that works when δ<(7-2√7)/6≈0.284. In the same work, the bound was further improved to δ<1-1/≈2≈0.292. Thus far, the small inverse problem has also been analyzed for an arbitrary β. Generalizations of Boneh and Durfee's lattices to obtain the stronger bound yielded the bound δ<1-≈β. However, the algorithm works only when β≥1/4. When 0<β<1/4, there have been several works where the authors claimed their results are the best. In this paper, we revisit the problem for an arbitrary β. At first, we summarize the previous results for 0<β<1/4. We reveal that there are some results that are not valid and show that Weger's algorithms provide the best bounds. Next, we propose an improved algorithm to solve the problem for 0<β<1/4. Our algorithm works when δ<1-2(≈β(3+4β)-β)/3. Our algorithm construction is based on the combinations of Boneh and Durfee's two forms of lattices and it is more natural compared with previous works. For the cryptographic application, we introduce small secret exponent attacks on Multi-Prime RSA with small prime differences.

In this paper, we present a lattice based method on small secret exponent attack on the RSA scheme. Boneh and Durfee reduced the attack to finding the small roots of the bivariate modular equation: x(N+1+y)+1 ≡ 0 (mod e), where N is an RSA modulus and e is the RSA public key and proposed a lattice based algorithm for solving the problem. When the secret exponent d is less than N0.292, their method breaks the RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blömer and May proposed an alternative algorithm that uses a full-rank lattice, even though it gives a bound (d≤N0.290) that is worse than Boneh-Durfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the Boneh-Durfee's bound: d≤N0.292. In this paper, we first give an elementary proof for achieving Blömer-May's bound: d≤N0.290. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of Blömer-May's proof. We then provide a unified framework — which subsumes the two previous methods, the Herrmann-May and the Blömer-May methods, as a special case — for constructing a lattice that can be are used to solve the problem. In addition, we prove that Boneh-Durfee's bound: d≤N0.292 is still optimal in our unified framework.

We introduce a “generalized small inverse problem (GSIP)” and present an algorithm for solving this problem. GSIP is formulated as finding small solutions of f(x0, x1, ..., xn)=x0 h(x1, ..., xn)+C=0 (mod ; M) for an n-variate polynomial h, non-zero integers C and M. Our algorithm is based on lattice-based Coppersmith technique. We provide a strategy for construction of a lattice basis for solving f=0, which is systematically transformed from a lattice basis for solving h=0. Then, we derive an upper bound such that the target problem can be solved in polynomial time in log M in an explicit form. Since GSIPs include some RSA-related problems, our algorithm is applicable to them. For example, the small key attacks by Boneh and Durfee are re-found automatically.

This paper shows that there is a fruitful world behind sampling theorems. For this purpose, the sampling problem is reformulated from a functional analytic standpoint, and is consequently revealed that the sampling problem is a kind of inverse problem. The sampling problem covers, for example, signal and image restoration including super resolution, image reconstruction from projections such as CT scanners in hospitals, and supervised learning such as learning in artificial neural networks. An optimal reconstruction operator is also given, providing the best approximation to an individual original signal without our knowing the original signal.

UWB pulse radars enable us to measure a target location with high range-resolution, and so are applicable for measurement systems for robots and automobile. We have already proposed a robust and fast imaging algorithm with an envelope of circles, which is suitable for these applications. In this method, we determine time delays from received signals with the matched filter for a transmitted waveform. However, scattered waveforms are different from transmitted one depending on the target shape. Therefore, the resolution of the target edges deteriorates due to these waveform distortions. In this paper, a high-resolution imaging algorithm for convex targets is proposed by iteration of the shape and waveform estimation. We show application examples with numerical simulations and experiments, and confirm its capability to detect edges of an object.

Magnetoencephalography (MEG) is a method to measure a magnetic field generated by electrical neural activity in a brain, and it plays increasingly important role in clinical diagnoses and neurophysiological studies. However, in MEG analysis, the estimation of the brain activity, of the electric current density distribution in a brain which is represented by current dipoles, is problematic. A spatial filter and subsequent reconstruction of the current density distribution estimated by the spatial filter (spatial filtered reconstruction: SFR) are proposed. The spatial filter is designed to be used without prior or temporal information. The proposed spatial filter ensures that it concentrates the current distribution around the activated sources in the conductor. The current distribution estimated by the spatial filter is reconstructed by multiple linear regression. Redundant current dipoles are eliminated, and the current distribution is optimized in the sense of the Mallows Cp statistic. Numerical studies are demonstrated and show successful estimation by SFR in multiple-dipole cases. In single-dipole cases with SNRs of 101 and more, the location of the true dipole was successfully estimated for about 80% of the simulations. The reconstruction with multiple linear regression corrected the location of the maximum current density estimated by the proposed spatial filtering. The dipole on the correct position contributes to more than 70% of the total dipoles in the estimated current distribution in those cases. These results show that the current distribution is effectively localized by SFR. We also investigate the differences among SFR, the LCMV (linearly constrained minimum variance) beamformer and the SAM (synthetic aperture magnetometry), the representatives of spatial filters in MEG analyses. It is indicated that spatial resolution is improved by avoiding dependence on temporal information.

This paper presents a computational approach to the imaging of a partially immersed conducting cylinder. Both cubic-spline method and trigonometric series for shape description are used and compared. Based on the boundary condition and the recorded scattered field, a set of nonlinear integral equations is derived and the imaging problem is reformulated into an optimization problem. The genetic algorithm is employed to find out the global extreme solution of the object function. It is found that the shape described by Fourier series can be reconstructed by cubic-spline. In the opposite case, the shape described by cubic-spline and reconstructed by Fourier series expansion will fail. Even when the initial guess is far away from the exact one, the cubic-spline expansion and genetic algorithm can avoid the local extreme and converge to a global extreme solution. Numerical results are given to show that the shape description by using cubic-spline method is much better than that by the Fourier series. In addition, the effect of Gaussian noise on the reconstruction is investigated.

Imaging techniques for robots are important and meaningful in the near future. Pulse radar systems have a great potential for shape estimation and locationing of targets. They have an advantage that they can be used even in critical situations where optical techniques cannot be used. It is thus required to develop high-resolution imaging algorithms for pulse radar systems. High-resolution imaging algorithms utilize the carrier phase of received signals. However, their estimation accuracy suffers degradation due to phase rotation of the received signal because the phase depends on the shape of the target. In this paper, we propose a phase compensation algorithm for high-resolution pulse radar systems. The proposed algorithm works well with SEABED algorithm, which is a non-parametric algorithm of estimating target shapes based on a reversible transform. The theory is presented first and numerical simulation results follow. We show the estimation accuracy is remarkably improved without sacrificing the resolution using the proposed algorithm.

Environment measurement is an important issue for various applications including household robots. Pulse radars are promising candidates in a near future. Estimating target shapes using waveform data, which we obtain by scanning an omni-directional antenna, is known as one of ill-posed inverse problems. Parametric methods such as Model-fitting method have problems concerning calculation time and stability. We propose a non-parametric algorithm for high-resolution estimation of target shapes in order to solve the problems of parametric algorithms.

This paper provides a review on the optimal design of photonic bandgap structures by inverse problem techniques. An overview of inverse problems techniques is given, with a special focus on topology design methods. A review of first applications of inverse problems techniques to photonic bandgap structures and waveguides is given, as well as some model problems, which provide a deeper insight into the structure of the optimal design problems.

Making up an electromagnetic wave simulator based on the FEM is tried, which may run on some widely used platforms by use of Java and a single commercial tool. Since the codes and configuration files to be created for this simulator are common, one can construct the simulator running on the platforms at the same time. Using this simulator, the transmission properties of two- and three-dimensional waveguide discontinuities in optical and microwave waveguides are analyzed, the inverse problem in material constant measurement is solved, and the computed results are presented including plots of the electric field distribution.

The objective of this study was to explore suitable spatial filters for inverse estimation of cortical potentials from the scalp electroencephalogram. The effect of incorporating noise covariance into inverse procedures was examined by computer simulations. The parametric projection filter, which allows inverse estimation with the presence of information on the noise covariance, was applied to an inhomogeneous three-concentric-sphere model under various noise conditions in order to estimate the cortical potentials from the scalp potentials. The present simulation results suggest that incorporation of information on the noise covariance allows better estimation of cortical potentials, than inverse solutions without knowledge about the noise covariance, when the correlation between the signal and noise is low. The method for determining the optimum regularization parameter, which can be applied for parametric inverse techniques, is also discussed.

Generalized Pulse Spectrum Technique (GPST) is a method to solve the inverse problems of wave-propagation and diffusion-dominated phenomena, and therefore has been popularly applied in image reconstruction of time-resolved diffuse optical tomography. With a standard GPST for simultaneous reconstruction of absorption and scattering coefficients, the products of the gradients of the Green's function and the photon-density flux, based on the photon-diffusion equation, are required to calculate the diffusion-related Jacobian matrix. The adversities are of two-folds: time-consuming and singular in the field near the source. The latter causes a severe insensitivity of the algorithm to the scattering changes deep inside tissue. To cope with the above difficulties, we propose in this paper a modified GPST algorithm that only involves the Green's function and the photon-density flux themselves in the scattering-related matrix. Our simulated and experimental reconstructions show that the modified algorithm can significantly improve the quality of scattering image and accelerate the reconstruction process, without an evident degradation in absorption image.

The scatterometer is a real aperture radar capable to perform a set of normalized radar cross section measurements under different azimuth angles for each resolution cell. The main field of application of a wind scatterometer regards the sea surface wind field determination. As a matter of fact, once such measurements have been performed it is possible to determine the sea surface wind field by means of an inversion procedure. In this paper we present a novel inversion scheme which is an evolution of the procedure nowday used by the Italian Space Agency (ASI) under the Italian Processing and Archiving Facility (I-PAF). A full comparative study shows that the novel inversion scheme better behaves whenever light wind regimes are in question.

A novel inverse scattering approach is developed to the reconstruction of electrical property distributions of a two-dimensional biaxial anisotropic object using time-domain scattering data. The approach is an extension of the forward-backward time-stepping (FBTS) algorithm previously described for an isotropic object. Synthetic examples of inversion are given to assess the effectiveness of the proposed method.

This paper deals with a quantitative inversion algorithm for reconstructing the permittivity and conductivity profiles of bounded inhomogeneous buried objects from measured multifrequency and multiincidence backscattered field data. An Edge-Preserving regularization scheme is applied leading to a significant enhancement in the profiles reconstructions. The applications concern civil engineering and geophysics as well as mine detection and localization. The performance of the reconstructions are illustrated with different synthetic data.