We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including covariance sketching, phase retrieval, quantum state tomography, and learning shallow polynomial neural networks, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex least-squares loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is bounded by a constant, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample complexity and computational complexity. To the best of our knowledge, this is the first guarantee that achieves near-optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.

We consider the problem of recovering low-rank matrices from random rank-one measurements, which spans numerous applications including phase retrieval, quantum state tomography, and learning shallow neural networks with quadratic activations, among others. Our approach is to directly estimate the low-rank factor by minimizing a nonconvex least-squares loss function via vanilla gradient descent, following a tailored spectral initialization. When the true rank is small, this algorithm is guaranteed to converge to the ground truth (up to global ambiguity) with near-optimal sample and computational complexities with respect to the problem size. To the best of our knowledge, this is the first theoretical guarantee that achieves near optimality in both metrics. In particular, the key enabler of near-optimal computational guarantees is an implicit regularization phenomenon: without explicit regularization, both spectral initialization and the gradient descent iterates automatically stay within a region incoherent with the measurement vectors. This feature allows one to employ much more aggressive step sizes compared with the ones suggested in prior literature, without the need of sample splitting.

In many signal processing tasks, one seeks to recover an rcolumn matrix object X ϵ ℂn×rfrom a set of nonnegative quadratic measurements up to orthonormal transforms. Example applications include coherence retrieval in optical imaging and covariance sketching for high-dimensional streaming data. To this end, efficient nonconvex optimization methods are quite appealing, due to their computational efficiency and scalability to large-scale problems. There is a recent surge of activities in designing nonconvex methods for the special case r = 1, known as phase retrieval; however, very little work has studied the general rank-r setting. Motivated by the success of phase retrieval, in this paper we derive several algorithms which utilize the quadratic loss function based on amplitude measurements, including (stochastic) gradient descent and alternating minimization. Numerical experiments demonstrate their computational and statistical performances, highlighting the superior performance of stochastic gradient descent with appropriate mini-batch sizes.

We address the problem of estimating a low-rank positive semidefinite (PSD) matrix from a set of magnitude measurements that are quadratic in the sensing vectors in the presence of arbitrary outliers. We propose a parameter-free algorithm that seeks the PSD matrix that minimizes the ℓ1-norm of the measurement residual. It is shown that the algorithm can exactly recover a rank-r PSD matrix of size-n from O (nr2) measurements with high probability, even when a fraction of the measurements is corrupted by arbitrary outliers. Furthermore, the recovery is also robust to bounded noise. When an upper bound of the rank of the PSD matrix is known a priori, we further propose a non-convex algorithm based on subgradient descent that demonstrates superior empirical performance.

We consider simultaneously identifying the membership and locations of point sources that are convolved with different low-pass point spread functions, from the observation of their superpositions. This problem arises in three-dimensional super-resolution single-molecule imaging, neural spike sorting, multi-user channel identification, among others. We propose a novel algorithm, based on convex programming, and establish its near-optimal performance guarantee for exact recovery by exploiting the sparsity of the point source model as well as incoherence between the point spread functions. Numerical examples are provided to demonstrate the effectiveness of the proposed approach.