Paper Info
Title
TARM: A Turbo-type Algorithm for Affine Rank Minimization.
Abstract
The affine rank minimization (ARM) problem arises in many real-world applications. The goal is to recover a low-rank matrix from a small amount of noisy affine measurements. The original problem is NP-hard, and so directly solving the problem is computationally prohibitive. Approximate low-complexity solutions for ARM have recently attracted much research interest. In this paper, we design an iterative algorithm for ARM based on message passing principles. The proposed algorithm is termed turbo-type ARM (TARM), as inspired by the recently developed turbo compressed sensing algorithm for sparse signal recovery. We show that, when the linear operator for measurement is right-orthogonally invariant (ROIL), a scalar function called state evolution can be established to accurately predict the behaviour of the TARM algorithm. We also show that TARM converges much faster than the counterpart algorithms for low-rank matrix recovery. We further extend the TARM algorithm for matrix completion, where the measurement operator corresponds to a random selection matrix. We show that, although the state evolution is not accurate for matrix completion, the TARM algorithm with carefully tuned parameters still significantly outperforms its counterparts.
Year
DOI
Venue
2018
10.1109/TSP.2019.2944740
IEEE Transactions on Signal Processing
Keywords
Field
DocType
Signal processing algorithms,Message passing,Minimization,Approximation algorithms,Prediction algorithms,Compressed sensing,Noise measurement
Affine transformation,Matrix completion,Matrix (mathematics),Iterative method,Algorithm,Invariant (mathematics),Operator (computer programming),Linear map,Mathematics,Compressed sensing
Journal
Volume
Issue
ISSN
abs/1802.03704
22
1053-587X
Citations 
PageRank 
References 
0
0.34
18
Authors
4
Name
Order
Citations
PageRank
Zhipeng Xue141.76
Xiao-jun Yuan299486.74
Junjie Ma314815.24
Yi Ma414931536.21