ADMiRA
ADMiRA: Atomic Decomposition for Minimum Rank Approximation. In this paper, we address compressed sensing of a low-rank matrix posing the inverse problem as an approximation problem with a specified target rank of the solution. A simple search over the target rank then provides the minimum rank solution satisfying a prescribed data approximation bound. We propose an atomic decomposition providing an analogy between parsimonious representations of a sparse vector and a low-rank matrix and extending efficient greedy algorithms from the vector to the matrix case. In particular, we propose an efficient and guaranteed algorithm named atomic decomposition for minimum rank approximation (ADMiRA) that extends Needell and Tropp’s compressive sampling matching pursuit (CoSaMP) algorithm from the sparse vector to the low-rank matrix case. The performance guarantee is given in terms of the rank-restricted isometry property (R-RIP) and bounds both the number of iterations and the error in the approximate solution for the general case of noisy measurements and approximately low-rank solution. With a sparse measurement operator as in the matrix completion problem, the computation in ADMiRA is linear in the number of measurements. Numerical experiments for the matrix completion problem show that, although the R-RIP is not satisfied in this case, ADMiRA is a competitive algorithm for matrix completion.
Keywords for this software
References in zbMATH (referenced in 31 articles , 2 standard articles )
Showing results 1 to 20 of 31.
Sorted by year (- Ma, Cong; Wang, Kaizheng; Chi, Yuejie; Chen, Yuxin: Implicit regularization in nonconvex statistical estimation: gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution (2020)
- Shen, Yuan; Liu, Xin: An alternating minimization method for matrix completion problems (2020)
- Tirer, Tom; Giryes, Raja: Generalizing CoSaMP to signals from a union of low dimensional linear subspaces (2020)
- Wei, Ke; Cai, Jian-Feng; Chan, Tony F.; Leung, Shingyu: Guarantees of Riemannian optimization for low rank matrix completion (2020)
- Yu, Ming; Gupta, Varun; Kolar, Mladen: Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach (2020)
- Park, Dohyung; Kyrillidis, Anastasios; Caramanis, Constantine; Sanghavi, Sujay: Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably (2018)
- Wang, Wendong; Wang, Jianjun: Enhancing matrix completion using a modified second-order total variation (2018)
- Bouwmans, Thierry; Sobral, Andrews; Javed, Sajid; Jung, Soon Ki; Zahzah, El-Hadi: Decomposition into low-rank plus additive matrices for background/foreground separation: a review for a comparative evaluation with a large-scale dataset (2017)
- Kueng, Richard; Rauhut, Holger; Terstiege, Ulrich: Low rank matrix recovery from rank one measurements (2017)
- Mareček, Jakub; Richtárik, Peter; Takáč, Martin: Matrix completion under interval uncertainty (2017)
- Sun, Chuangchuang; Dai, Ran: Rank-constrained optimization and its applications (2017)
- Kabanava, Maryia; Kueng, Richard; Rauhut, Holger; Terstiege, Ulrich: Stable low-rank matrix recovery via null space properties (2016)
- Wei, Ke; Cai, Jian-Feng; Chan, Tony F.; Leung, Shingyu: Guarantees of Riemannian optimization for low rank matrix recovery (2016)
- Blanchard, Jeffrey D.; Tanner, Jared; Wei, Ke: CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion (2015)
- Boumal, Nicolas; Absil, P.-A.: Low-rank matrix completion via preconditioned optimization on the Grassmann manifold (2015)
- Cai, Yun; Li, Song: Convergence analysis of projected gradient descent for Schatten-(p) nonconvex matrix recovery (2015)
- Geng, Juan; Wang, Laisheng; Wang, Yanfei: A non-convex algorithm framework based on DC programming and DCA for matrix completion (2015)
- Jin, Zheng-Fen; Wan, Zhongping; Zhao, Xiaoke; Xiao, Yunhai: A penalty decomposition method for rank minimization problem with affine constraints (2015)
- Wang, Zheng; Lai, Ming-Jun; Lu, Zhaosong; Fan, Wei; Davulcu, Hasan; Ye, Jieping: Orthogonal rank-one matrix pursuit for low rank matrix completion (2015)
- Zhang, Min; Yang, Lei; Huang, Zheng-Hai: Minimum ( n)-rank approximation via iterative hard thresholding (2015)