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.

References in zbMATH (referenced in 35 articles , 2 standard articles )

Showing results 1 to 20 of 35.
Sorted by year (citations)

1 2 next

  1. Héas, Patrick; Herzet, Cédric: Low-rank dynamic mode decomposition: an exact and tractable solution (2022)
  2. Adams, Henry; Kassab, Lara; Needell, Deanna: An adaptation for iterative structured matrix completion (2021)
  3. Bellavia, Stefania; Gondzio, Jacek; Porcelli, Margherita: A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion (2021)
  4. 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)
  5. Shen, Yuan; Liu, Xin: An alternating minimization method for matrix completion problems (2020)
  6. Tirer, Tom; Giryes, Raja: Generalizing CoSaMP to signals from a union of low dimensional linear subspaces (2020)
  7. Wei, Ke; Cai, Jian-Feng; Chan, Tony F.; Leung, Shingyu: Guarantees of Riemannian optimization for low rank matrix completion (2020)
  8. Yu, Ming; Gupta, Varun; Kolar, Mladen: Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach (2020)
  9. Tanner, Jared; Thompson, Andrew; Vary, Simon: Matrix rigidity and the ill-posedness of robust PCA and matrix completion (2019)
  10. Park, Dohyung; Kyrillidis, Anastasios; Caramanis, Constantine; Sanghavi, Sujay: Finding low-rank solutions via nonconvex matrix factorization, efficiently and provably (2018)
  11. Wang, Wendong; Wang, Jianjun: Enhancing matrix completion using a modified second-order total variation (2018)
  12. 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)
  13. Kueng, Richard; Rauhut, Holger; Terstiege, Ulrich: Low rank matrix recovery from rank one measurements (2017)
  14. Mareček, Jakub; Richtárik, Peter; Takáč, Martin: Matrix completion under interval uncertainty (2017)
  15. Sun, Chuangchuang; Dai, Ran: Rank-constrained optimization and its applications (2017)
  16. Kabanava, Maryia; Kueng, Richard; Rauhut, Holger; Terstiege, Ulrich: Stable low-rank matrix recovery via null space properties (2016)
  17. Wei, Ke; Cai, Jian-Feng; Chan, Tony F.; Leung, Shingyu: Guarantees of Riemannian optimization for low rank matrix recovery (2016)
  18. Blanchard, Jeffrey D.; Tanner, Jared; Wei, Ke: CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion (2015)
  19. Boumal, Nicolas; Absil, P.-A.: Low-rank matrix completion via preconditioned optimization on the Grassmann manifold (2015)
  20. Cai, Yun; Li, Song: Convergence analysis of projected gradient descent for Schatten-(p) nonconvex matrix recovery (2015)

1 2 next