We study the problem of estimating a low-rank positive semidefinite (PSD) matrix from a set of rank-one measurements using sensing vectors composed of i.i.d. standard Gaussian entries, which are possibly corrupted by arbitrary outliers. This problem arises from applications, such as phase retrieval, covariance sketching, quantum space tomography, and power spectrum estimation. We first propose a convex optimization algorithm that seeks the PSD matrix with the minimum @math -norm of the observation residual. The advantage of our algorithm is that it is free of parameters, therefore, eliminating the need for tuning parameters and allowing easy implementations. We establish that with high probability, a low-rank PSD matrix can be exactly recovered as soon as the number of measurements is large enough, even when a fraction of the measurements are corrupted by outliers with arbitrary magnitudes. Moreover, the recovery is also stable against bounded noise. With the additional information of an upper bound of the rank of the PSD matrix, we propose another nonconvex algorithm based on subgradient descent that demonstrates excellent empirical performance in terms of computational efficiency and accuracy.
In the absence of outliers, the PhaseLift algorithm in the following form where @math denotes the trace of @math , has been proposed to solve the phase retrieval problem @cite_13 @cite_25 @cite_0 . Later the same algorithm has been employed to recover low-rank PSD matrices in @cite_30 , where an order of @math measurements obtained from i.i.d. sub-Gaussian sensing vectors are shown to guarantee exact recovery in the noise-free case and stable recovery with bounded noise. One problem with the algorithm is that the noise bound @math is assumed known. Furthermore, it is not amenable to handle outliers, since @math can be arbitrarily large with outliers and consequently the ground truth @math quickly becomes infeasible for .
@cite_0 @cite_30 @cite_13 @cite_25
2102019642 2133105246 2078397124 2169501582
This paper develops a novel framework for phase retrieval, a problem which arises in X-ray crystallography, diffraction imaging, astronomical imaging, and many other applications. Our approach, called PhaseLift, combines multiple structured illuminations together with ideas from convex programming to recover the phase from intensity measurements, typically from the modulus of the diffracted wave. We demonstrate empirically that a complex-valued object can be recovered from the knowledge of the magnitude of just a few diffracted patterns by solving a simple convex optimization problem inspired by the recent literature on matrix completion. More importantly, we also demonstrate that our noise-aware algorithms are stable in the sense that the reconstruction degrades gracefully as the signal-to-noise ratio decreases. Finally, we introduce some theory showing that one can design very simple structured illumination patterns such that three diffracted figures uniquely determine the phase of the object we wish to... Statistical inference and information processing of high-dimensional data often require an efficient and accurate estimation of their second-order statistics. With rapidly changing data, limited processing power and storage at the acquisition devices, it is desirable to extract the covariance structure from a single pass over the data and a small number of stored measurements. In this paper, we explore a quadratic (or rank-one) measurement model which imposes minimal memory requirements and low computational complexity during the sampling process, and is shown to be optimal in preserving various low-dimensional covariance structures. Specifically, four popular structural assumptions of covariance matrices, namely, low rank, Toeplitz low rank, sparsity, jointly rank-one and sparse structure, are investigated, while recovery is achieved via convex relaxation paradigms for the respective structure. The proposed quadratic sampling framework has a variety of potential applications, including streaming data processing, high-frequency wireless communication, phase space tomography and phase retrieval in optics, and noncoherent subspace detection. Our method admits universally accurate covariance estimation in the absence of noise, as soon as the number of measurements exceeds the information theoretic limits. We also demonstrate the robustness of this approach against noise and imperfect structural assumptions. Our analysis is established upon a novel notion called the mixed-norm restricted isometry property (RIP- @math ), as well as the conventional RIP- @math for near-isotropic and bounded measurements. In addition, our results improve upon the best-known phase retrieval (including both dense and sparse signals) guarantees using PhaseLift with a significantly simpler approach. Suppose we wish to recover a signal amssym @math from m intensity measurements of the form , ; that is, from data in which phase information is missing. We prove that if the vectors are sampled independently and uniformly at random on the unit sphere, then the signal x can be recovered exactly (up to a global phase factor) by solving a convenient semidefinite program–-a trace-norm minimization problem; this holds with large probability provided that m is on the order of , and without any assumption about the signal whatsoever. This novel result demonstrates that in some instances, the combinatorial phase retrieval problem can be solved by convex programming techniques. Finally, we also prove that our methodology is robust vis-a-vis additive noise. © 2012 Wiley Periodicals, Inc. This note shows that we can recover any complex vector @math exactly from on the order of n quadratic equations of the form |?a i ,x 0?|2=b i , i=1,?,m, by using a semidefinite program known as PhaseLift. This improves upon earlier bounds in (Commun. Pure Appl. Math. 66:1241---1274, 2013), which required the number of equations to be at least on the order of nlogn. Further, we show that exact recovery holds for all input vectors simultaneously, and also demonstrate optimal recovery results from noisy quadratic measurements; these results are much sharper than previously known results.