Low rank models exist in many applications, ranging from signal processing to data analysis. Typical examples include low rank matrix completion, phase retrieval, and spectrally sparse signal reconstruction. We will present a class of computationally efficient algorithms which are universally applicable for those low rank reconstruction problems. Theoretical recovery guarantees will be established for the proposed algorithms under different random models, showing that the sampling complexity is essentially proportional to the intrinsic dimension of the problems rather the ambient dimension. Extensive numerical experiments demonstrate the efficacy of the algorithms.

海报