CoSaMP swMATH ID: 8727 Software Authors: Needell, D.; Tropp, J.A. Description: CoSaMP: Iterative signal recovery from incomplete and inaccurate samples. Compressive sampling offers a new paradigm for acquiring signals that are compressible with respect to an orthonormal basis. The major algorithmic challenge in compressive sampling is to approximate a compressible signal from noisy samples. This paper describes a new iterative recovery algorithm called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix-vector multiplies with the sampling matrix. For compressible signals, the running time is just \(O(Nlog ^{2}N)\), where \(N\) is the length of the signal. Homepage: http://www.sciencedirect.com/science/article/pii/S1063520308000638 Keywords: algorithms; approximation; basis pursuit; compressed sensing; orthogonal matching pursuit; restricted isometry property; signal recovery; sparse approximation; uncertainty principle Related Software: PDCO; SPGL1; CVX; NESTA; ADMiRA; glmnet; FPC_AS; TFOCS; TwIST; UNLocBoX; PhaseLift; GESPAR; L1-MAGIC; softImpute; Wirtinger Flow; SparsePR; ElemStatLearn; BLOOMP; PROPACK; GQTPAR Cited in: 267 Documents all top 5 Cited by 566 Authors 11 Needell, Deanna 9 Li, Song 8 Blanchard, Jeffrey D. 7 Rauhut, Holger 6 Foucart, Simon 6 Giryes, Raja 6 Krahmer, Felix 6 Tanner, Jared W. 6 Zhao, Yunbin 5 Iwen, Mark A. 5 Li, Shidong 5 Saab, Rayan 5 Wakin, Michael B. 5 Xiu, Naihua 4 Chen, Wengu 4 Daković, Miloš 4 Flinth, Axel 4 Fu, Fangwei 4 Lai, Mingjun 4 Lin, Junhong 4 Niu, Minyao 4 Stanković, Ljubiša 4 Temlyakov, Vladimir Nikolaevich 4 Wang, Gang 4 Zhou, Shenglong 3 Bouchot, Jean-Luc 3 Davenport, Mark A. 3 Davies, Mike E. 3 Elad, Michael 3 Ge, HuanMin 3 Hou, Thomas Yizhao 3 Kutyniok, Gitta 3 Lu, Xiliang 3 Qi, Houduo 3 Shi, Zuoqiang 3 Tropp, Joel A. 3 Yılmaz, Özgür 2 Baraniuk, Richard G. 2 Brunton, Steven L. 2 Cai, Jian-Feng 2 Cai, Yun 2 Calderbank, Arthur Robert 2 Candès, Emmanuel J. 2 Cartis, Coralia 2 Cevher, Volkan 2 Chen, Dirong 2 Chen, Jianli 2 Chen, Xuemei 2 Choi, Bosu 2 Dan, Wei 2 Doostan, Alireza 2 Eftekhari, Armin 2 Eisert, Jens 2 Fountoulakis, Kimon 2 Geng, Pengbo 2 Gondzio, Jacek 2 Gross, Benedict Hyman 2 Güntürk, Cemalettin Sinan 2 Han, Ningning 2 Huang, Wei 2 Ioana, Cornel 2 Jiao, Yuling 2 Jin, Bangti 2 Kočvara, Michal 2 Kutz, J. Nathan 2 Kyrillidis, Anastasios 2 Li, Ping 2 Li, Qia 2 Lian, Feng 2 Liu, Dekai 2 Liu, Jing 2 Ma, Anna 2 Mckenzie, Daniel 2 Meng, Nan 2 Möller, Michael 2 Nikolova, Mila 2 Obozinski, Guillaume 2 Peyré, Gabriel 2 Roth, Ingo 2 Ruan, Guoqing 2 Shen, Yi 2 Thompson, Andrew 2 Viswanathan, Aditya 2 Wang, Haichao 2 Wang, Jun 2 Wang, Rongrong 2 Wang, Xingtao 2 Wang, Yang 2 Ward, Rachel A. 2 Wei, Ke 2 Wen, Jinming 2 Wunder, Gerhard 2 Xiang, Jianhong 2 Xu, Fengmin 2 Yin, Xiangjun 2 Yue, Huihui 2 Zhang, Na 2 Zhang, Xiaoqun 2 Zhu, Wenxing 2 Zhu, Zhihui ...and 466 more Authors all top 5 Cited in 106 Serials 37 Applied and Computational Harmonic Analysis 13 Circuits, Systems, and Signal Processing 10 Science China. Mathematics 8 Mathematical Problems in Engineering 6 Inverse Problems 6 SIAM Journal on Imaging Sciences 5 Information Sciences 5 Journal of Computational and Applied Mathematics 5 Journal of Machine Learning Research (JMLR) 5 Inverse Problems and Imaging 4 Journal of Computational Physics 4 Mathematics of Computation 4 Signal Processing 4 Linear Algebra and its Applications 4 SIAM Journal on Optimization 4 SIAM Journal on Scientific Computing 4 Foundations of Computational Mathematics 3 Applied Mathematics and Computation 3 Journal of Approximation Theory 3 Journal of Global Optimization 3 Numerical Algorithms 3 The Journal of Fourier Analysis and Applications 3 Sampling Theory in Signal and Image Processing 3 Science China. Information Sciences 3 Information and Inference 3 Journal of the Operations Research Society of China 3 SIAM Journal on Mathematics of Data Science 2 Computer Methods in Applied Mechanics and Engineering 2 IEEE Transactions on Information Theory 2 Statistical Science 2 Multidimensional Systems and Signal Processing 2 Computational Statistics and Data Analysis 2 Mathematical Programming. Series A. Series B 2 Journal of Mathematical Imaging and Vision 2 Computational Optimization and Applications 2 Journal of Combinatorial Optimization 2 Journal of Applied Mathematics 2 Multiscale Modeling & Simulation 2 Mathematical Programming Computation 2 Symmetry 1 Communications on Pure and Applied Mathematics 1 Discrete Applied Mathematics 1 Journal of Fluid Mechanics 1 Journal of the Franklin Institute 1 Journal of Mathematical Analysis and Applications 1 The Annals of Statistics 1 Canadian Mathematical Bulletin 1 Journal of the American Statistical Association 1 Journal of Optimization Theory and Applications 1 Journal of Statistical Planning and Inference 1 Mathematics of Operations Research 1 Numerical Functional Analysis and Optimization 1 Numerische Mathematik 1 SIAM Journal on Numerical Analysis 1 Theoretical Computer Science 1 Journal of Computational Mathematics 1 Applied Numerical Mathematics 1 Acta Mathematicae Applicatae Sinica. English Series 1 Probability Theory and Related Fields 1 Journal of Complexity 1 Constructive Approximation 1 Algorithmica 1 Discrete & Computational Geometry 1 Asia-Pacific Journal of Operational Research 1 Journal of Scientific Computing 1 Neural Networks 1 Machine Learning 1 Geometric and Functional Analysis. GAFA 1 Automation and Remote Control 1 SIAM Journal on Mathematical Analysis 1 SIAM Review 1 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 1 Cybernetics and Systems Analysis 1 Numerical Linear Algebra with Applications 1 Finite Fields and their Applications 1 Advances in Computational Mathematics 1 Annals of Mathematics and Artificial Intelligence 1 Optimization Methods & Software 1 Journal of Inequalities and Applications 1 Archives of Computational Methods in Engineering 1 Sādhanā 1 Communications on Pure and Applied Analysis 1 ACM Journal of Experimental Algorithmics 1 Analysis and Applications (Singapore) 1 International Journal of Wavelets, Multiresolution and Information Processing 1 Acta Numerica 1 Journal of Industrial and Management Optimization 1 Inverse Problems in Science and Engineering 1 GAMM-Mitteilungen 1 Optimization Letters 1 Computational & Mathematical Methods in Medicine 1 Journal of Physics A: Mathematical and Theoretical 1 Asian-European Journal of Mathematics 1 Discrete Mathematics, Algorithms and Applications 1 Algorithms 1 Cryptography and Communications 1 Journal of Computational and Graphical Statistics 1 Communications in Mathematics and Statistics 1 Computer Science Review 1 Journal of Computational Dynamics ...and 6 more Serials all top 5 Cited in 24 Fields 172 Information and communication theory, circuits (94-XX) 96 Numerical analysis (65-XX) 75 Operations research, mathematical programming (90-XX) 42 Computer science (68-XX) 36 Statistics (62-XX) 24 Linear and multilinear algebra; matrix theory (15-XX) 17 Harmonic analysis on Euclidean spaces (42-XX) 15 Calculus of variations and optimal control; optimization (49-XX) 15 Probability theory and stochastic processes (60-XX) 14 Approximations and expansions (41-XX) 8 Operator theory (47-XX) 7 Biology and other natural sciences (92-XX) 6 Partial differential equations (35-XX) 4 Dynamical systems and ergodic theory (37-XX) 4 Fluid mechanics (76-XX) 2 Functional analysis (46-XX) 2 Systems theory; control (93-XX) 1 Number theory (11-XX) 1 Special functions (33-XX) 1 Ordinary differential equations (34-XX) 1 Integral equations (45-XX) 1 Convex and discrete geometry (52-XX) 1 Differential geometry (53-XX) 1 Optics, electromagnetic theory (78-XX) Citations by Year