From compressed sensing to low-rank matrix recovery: Theory and applications

This paper reviews the basic theory and typical applications of compressed sensing, matrix rank minimization, and low-rank matrix recovery. Compressed sensing based on convex optimization and related matrix rank minimization and low-rank matrix recovery are hot research topics in recent years. They find many important and successful applications in different research fields, including signal processing, recommending system, high-dimensional data analysis, image processing, computer vision and many others. In these real applications, analysis and processing of high-dimensional data are often involved, which needs to utilize the structure of data, such as sparsity or low rank property of the data matrix, sufficiently and reasonably. Although minimization of objective functions like sparsity or matrix rank is NP-hard in the worst case, by optimizing the convex relaxation of the original objective function under certain reasonable assumptions, convex optimization could give the optimal solution of the original problem. Moreover, many efficient convex optimization algorithms could be used for solving the problem and are also applicable to large-scale problems. In this paper, we first review the fundamental theories about compressed sensing, matrix rank minimization, and low-rank matrix recovery. Then, we introduce the typical applications of these theories in image processing, computer vision, and computational photography. We also look into the future work in related research areas. Copyright © 2013 Acta Automatica Sinica. All rights reserved.