ADMiRA swMATH ID: 31664 Software Authors: Lee, Kiryung; Bresler, Yoram Description: 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. Homepage: https://ieeexplore.ieee.org/document/5550497 Related Software: CoSaMP; LMaFit; PROPACK; softImpute; PhaseLift; Wirtinger Flow; RTRMC; SDPLR; Optspace; Jellyfish; SDPT3; PDCO; SPGL1; Eigentaste; CVX; SeDuMi; ElemStatLearn; Manopt; GitHub; redbKIT Cited in: 35 Documents Standard Articles 2 Publications describing the Software, including 2 Publications in zbMATH Year Corrections to “ADMiRA: atomic decomposition for minimum rank approximation”. Zbl 1364.94134Lee, Kiryung; Bresler, Yoram 2013 ADMiRA: atomic decomposition for minimum rank approximation. Zbl 1366.94112Lee, Kiryung; Bresler, Yoram 2010 all top 5 Cited by 87 Authors 3 Wei, Ke 2 Bresler, Yoram 2 Cai, Jian-Feng 2 Cevher, Volkan 2 Chan, Tony Fan-Cheong 2 Kueng, Richard 2 Kyrillidis, Anastasios 2 Lee, Kiryung 2 Leung, Shingyu 2 Li, Song 2 Needell, Deanna 2 Rauhut, Holger 2 Tanner, Jared W. 2 Terstiege, Ulrich 1 Absil, Pierre-Antoine 1 Adams, Henry 1 Bellavia, Stefania 1 Blanchard, Jeffrey D. 1 Bonnabel, Silvère 1 Boumal, Nicolas 1 Bouwmans, Thierry 1 Cai, Yun 1 Caramanis, Constantine 1 Chen, Dirong 1 Chen, Yuxin 1 Chi, Yuejie 1 Dai, Ran 1 Davulcu, Hasan 1 Doan, Xuan Vinh 1 Eldar, Yonina Chana 1 Fan, Wei 1 Geng, Juan 1 Giryes, Raja 1 Goldfarb, Donald 1 Gondzio, Jacek 1 Héas, Patrick 1 Herzet, Cédric 1 Huang, Wei 1 Huang, Zheng-Hai 1 Javed, Sajid 1 Jin, Zhengfen 1 Jung, Soon Ki 1 Kabanava, Maryia 1 Kassab, Lara 1 Kolar, Mladen 1 Lai, Mingjun 1 Lin, Junhong 1 Liu, Lu 1 Liu, Xin 1 Lu, Zhaosong 1 Ma, Cong 1 Ma, Shiqian 1 Mareček, Jakub 1 Meyer, Gilles 1 Mishra, Bamdev 1 Park, Dohyung 1 Plan, Yaniv 1 Porcelli, Margherita 1 Richtárik, Peter 1 Sanghavi, Sujay 1 Sepulchre, Rodolphe J. 1 Shen, Yuan 1 Sobral, Andrews 1 Sun, Chuangchuang 1 Takáč, Martin 1 Thompson, Andrew 1 Tirer, Tom 1 Tyagi, Hemant 1 Vary, Simon 1 Vavasis, Stephen A. 1 Wan, Zhongping 1 Wang, Jianjun 1 Wang, Kaizheng 1 Wang, Laisheng 1 Wang, Wendong 1 Wang, Yanfei 1 Wang, Zheng 1 Wen, Zaiwen 1 Xiao, Yunhai 1 Yang, Lei 1 Ye, Jieping 1 Yin, Wotao 1 Yu, Ming 1 Zahzah, El-hadi 1 Zhang, Min 1 Zhang, Yin 1 Zhao, Xiaoke all top 5 Cited in 28 Serials 5 Applied and Computational Harmonic Analysis 2 IEEE Transactions on Information Theory 2 Foundations of Computational Mathematics 2 Information and Inference 1 Applied Mathematics and Computation 1 Automatica 1 Journal of Computational and Applied Mathematics 1 SIAM Journal on Matrix Analysis and Applications 1 Journal of Scientific Computing 1 Journal of Global Optimization 1 Numerical Algorithms 1 Computational Statistics 1 Applied Mathematical Modelling 1 European Journal of Operational Research 1 Linear Algebra and its Applications 1 Journal of Mathematical Imaging and Vision 1 Journal of Nonlinear Science 1 SIAM Journal on Scientific Computing 1 Discrete Dynamics in Nature and Society 1 Inverse Problems and Imaging 1 Electronic Journal of Statistics 1 SIAM Journal on Imaging Sciences 1 Discrete and Continuous Dynamical Systems. Series S 1 Mathematical Programming Computation 1 Science China. Mathematics 1 Computer Science Review 1 Foundations of Data Science 1 SIAM Journal on Mathematics of Data Science all top 5 Cited in 11 Fields 22 Numerical analysis (65-XX) 18 Linear and multilinear algebra; matrix theory (15-XX) 16 Operations research, mathematical programming (90-XX) 6 Information and communication theory, circuits (94-XX) 4 Computer science (68-XX) 3 Statistics (62-XX) 2 Differential geometry (53-XX) 2 Systems theory; control (93-XX) 1 Approximations and expansions (41-XX) 1 Probability theory and stochastic processes (60-XX) 1 Quantum theory (81-XX) Citations by Year