Albert Fannjiang

Wenjing Liao, Albert Fannjiang

This paper studies the problem of line spectral estimation in the continuum of a bounded interval with one snapshot of array measurement. The single-snapshot measurement data is turned into a Hankel data matrix which admits the Vandermonde decomposition and is suitable for the MUSIC algorithm. The MUSIC algorithm amounts to finding the null space (the noise space) of the Hankel matrix, forming the noise-space correlation function and identifying the s smallest local minima of the noise-space correlation as the frequency set. In the noise-free case exact reconstruction is guaranteed for any arbitrary set of frequencies as long as the number of measurements is at least twice the number of distinct frequencies to be recovered. In the presence of noise the stability analysis shows that the perturbation of the noise-space correlation is proportional to the spectral norm of the noise matrix as long as the latter is smaller than the smallest (nonzero) singular value of the noiseless Hankel data matrix. Under the assumption that frequencies are separated by at least twice the Rayleigh Length (RL), the stability of the noise-space correlation is proved by means of novel discrete Ingham inequalities which provide bounds on nonzero singular values of the noiseless Hankel data matrix. The numerical performance of MUSIC is tested in comparison with other algorithms such as BLO-OMP and SDP (TV-min). While BLO-OMP is the stablest algorithm for frequencies separated above 4 RL, MUSIC becomes the best performing one for frequencies separated between 2 RL and 3 RL. Also, MUSIC is more efficient than other methods. MUSIC truly shines when the frequency separation drops to 1 RL or below when all other methods fail. Indeed, the resolution length of MUSIC decreases to zero as noise decreases to zero as a power law with an exponent much smaller than an upper bound established by Donoho.

Pengwen Chen, Albert Fannjiang, Gi-Ren Liu

Alternating projection (AP) of various forms, including the Parallel AP (PAP), Real-constrained AP (RAP) and the Serial AP (SAP), are proposed to solve phase retrieval with at most two coded diffraction patterns. The proofs of geometric convergence are given with sharp bounds on the rates of convergence in terms of a spectral gap condition. To compensate for the local nature of convergence, the null initialization is proposed for initial guess and proved to produce asymptotically accurate initialization for the case of Gaussian random measurement. Numerical experiments show that the null initialization produces more accurate initial guess than the spectral initialization and that AP converges faster to the true object than other iterative schemes for non-convex optimization such as the Wirtinger Flow. In numerical experiments, AP with the null initialization converges globally to the true object.

Albert Fannjiang, Wenjing Liao

Highly coherent sensing matrices arise in discretization of continuum problems such as radar and medical imaging when the grid spacing is below the Rayleigh threshold as well as in using highly coherent, redundant dictionaries as sparsifying operators. Algorithms (BOMP, BLOOMP) based on techniques of band exclusion and local optimization are proposed to enhance Orthogonal Matching Pursuit (OMP) and deal with such coherent sensing matrices. BOMP and BLOOMP have provably performance guarantee of reconstructing sparse, widely separated objects {\em independent} of the redundancy and have a sparsity constraint and computational cost similar to OMP's. Numerical study demonstrates the effectiveness of BLOOMP for compressed sensing with highly coherent, redundant sensing matrices.

Albert Fannjiang, Weilin Li

We develop a multidimensional version of Gradient-MUSIC for estimating the frequencies of a nonharmonic signal from noisy samples. The guiding principle is that frequency recovery should be based only on the signal subspace determined by the data. From this viewpoint, the MUSIC functional is an economical nonconvex objective encoding the relevant information, and the problem becomes one of understanding the geometry of its perturbed landscape. Our main contribution is a general structural theory showing that, under explicit conditions on the measurement kernel and the perturbation of the signal subspace, the perturbed MUSIC function is an admissible optimization landscape: suitable initial points can be found efficiently by coarse thresholding, gradient descent converges to the relevant local minima, and these minima obey quantitative error bounds. Thus the theory is not merely existential; it provides a constructive global optimization framework for multidimensional optimal resolution. We verify the abstract conditions in detail for two canonical sampling geometries: discrete samples on a cube and continuous samples on a ball. In both cases we obtain uniform, nonasymptotic recovery guarantees under deterministic as well as stochastic noise. In particular, for lattice samples in a cube of side length $4m$, if the true frequencies are separated by at least $β_d/m$ and the noise has $\ell^\infty$ norm at most $\varepsilon$, then Gradient-MUSIC recovers the frequencies with error at most \[ C_d \frac{\varepsilon}{m}, \] where $C_d, β_d>0$ depend only on the dimension. This scaling is minimax optimal in $m$ and $\varepsilon$. Under stationary Gaussian noise, the error improves to \[ C_d\frac{σ\sqrt{\log(m)}}{m^{1+d/2}}. \] This is the noisy super-resolution scaling: (see paper for rest of abstract)

Pengwen Chen, Albert Fannjiang

Uniqueness of solution is proved for any ptychographic scheme with a random masks under a minimum overlap condition and local geometric convergence analysis is given for the alternating projection (AP) and Douglas-Rachford (DR) algorithms. DR is shown to possess a unique fixed point in the object domain and for AP a simple criterion for distinguishing the true solution among possibly many fixed points is given. A minimalist scheme is proposed where the adjacent masks overlap 50\% of area and each pixel of the object is illuminated by exactly four times during the whole measurement process. Such a scheme is conveniently parametrized by the number $q$ of shifted masks in each direction. The lower bound $1-C/q^2$ is proved for the geometric convergence rate of the minimalist scheme, predicting a poor performance with large $q$ which is confirmed by numerical experiments. Extensive numerical experiments are performed to explore what the general features of a well-performing mask are like, what the best-performing values of $q$ for a given mask are, how robust the minimalist scheme is with respect to measurement noise and what the significant factors affecting the noise stability are.