Iterative Concave Rank Approximation for Recovering Low-Rank Matrices

Abstract

In this paper, we propose a new algorithm for recovery of low-rank matrices from compressed linear measurements. The underlying idea of this algorithm is to closely approximate the rank function with a smooth function of singular values, and then minimize the resulting approximation subject to the linear constraints. The accuracy of the approximation is controlled via a scaling parameter $\delta$, where a smaller $\delta$ corresponds to a more accurate fitting. The consequent optimization problem for any finite $\delta$ is nonconvex. Therefore, in order to decrease the risk of ending up in local minima, a series of optimizations is performed, starting with optimizing a rough approximation (a large $\delta$) and followed by successively optimizing finer approximations of the rank with smaller $\delta$'s. To solve the optimization problem for any $\delta >0$, it is converted to a new program in which the cost is a function of two auxiliary positive semidefinete variables. The paper shows that this new program is concave and applies a majorize-minimize technique to solve it which, in turn, leads to a few convex optimization iterations. This optimization scheme is also equivalent to a reweighted Nuclear Norm Minimization (NNM), where weighting update depends on the used approximating function. For any $\delta >0$, we derive a necessary and sufficient condition for the exact recovery which are weaker than those corresponding to NNM. On the numerical side, the proposed algorithm is compared to NNM and a reweighted NNM in solving affine rank minimization and matrix completion problems showing its considerable and consistent superiority in terms of success rate, especially, when the number of measurements decreases toward the lower-bound for the unique representation.

IEEE Trans. on Signal Processing, vol. 62, no. 20

References in corpus (3)

• A fast approach for overcomplete sparse decomposition based on smoothed L0 norm
• Recovery of Low-Rank Matrices under Affine Constraints via a Smoothed Rank Function
• DOA Estimation in Partially Correlated Noise Using Low-Rank/Sparse Matrix Decomposition

Cited by in corpus (7)

• ${\ell }_0$-Motivated Low-Rank Sparse Subspace Clustering
• A Class of Nonconvex Penalties Preserving Overall Convexity in Optimization-Based Mean Filtering
• Successive Concave Sparsity Approximation for Compressed Sensing
• Nonconvex and Nonsmooth Sparse Optimization via Adaptively Iterative Reweighted Methods
• Deep Unfolding of Iteratively Reweighted ADMM for Wireless RF Sensing
• Defect Detection by MIMO Wireless Sensing based on Weighted Low-Rank plus Sparse Recovery
• Upper Bounds on the Error of Sparse Vector and Low-Rank Matrix Recovery