Iterative Concave Rank Approximation for Recovering Low-Rank Matrices

DOI10.1109/TSP.2014.2340820MaRDI QIDQ4579496zbMATH OpenOpenAlexFDO

Authors Mohammadreza Malek-Mohammadi, Massoud Babaie-Zadeh, Mikael Skoglund

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01158

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

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.

Cited in

(12)

• Proximal iteratively reweighted algorithm for low-rank matrix recovery
• Convex low rank approximation
• Nonconvex and nonsmooth sparse optimization via adaptively iterative reweighted methods
• A non-convex tensor rank approximation for tensor completion
• Low-Rank Matrix Estimation from Rank-One Projections by Unlifted Convex Optimization
• Matrix completion via minimizing an approximate rank
• scientific article; zbMATH DE number 6276219 (Why is no real title available?)
• Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications
• Sparse recovery based on the generalized error function
• Inexact proximal point method with a Bregman regularization for quasiconvex multiobjective optimization problems via limiting subdifferentials
• Matrix-free Krylov iteration for implicit convolution of numerically low-rank data
• Ellipse fitting via low-rank generalized multidimensional scaling matrix recovery

This page was built for publication: Iterative Concave Rank Approximation for Recovering Low-Rank Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4579496)