## 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; glmnet; FPC_AS; ADMiRA; TFOCS; PhaseLift; GESPAR; UNLocBoX; TwIST; Wirtinger Flow; SparsePR; ElemStatLearn; BLOOMP; softImpute; L1-MAGIC; GQTPAR; PROPACK Referenced in: 253 Publications
all top 5

### Referenced by 531 Authors

 11 Needell, Deanna 8 Blanchard, Jeffrey D. 8 Li, Song 7 Rauhut, Holger 6 Foucart, Simon 6 Giryes, Raja 6 Krahmer, Felix 6 Tanner, Jared W. 5 Iwen, Mark A. 5 Li, Shidong 5 Saab, Rayan 5 Wakin, Michael B. 5 Zhao, Yunbin 4 Chen, Wengu 4 Daković, Miloš 4 Fu, Fangwei 4 Lin, Junhong 4 Niu, Minyao 4 Stanković, Ljubiša 4 Temlyakov, Vladimir Nikolaevich 4 Wang, Gang 4 Xiu, Naihua 4 Zhou, Shenglong 3 Bouchot, Jean-Luc 3 Davenport, Mark A. 3 Davies, Mike E. 3 Elad, Michael 3 Flinth, Axel 3 Ge, HuanMin 3 Hou, Thomas Yizhao 3 Kutyniok, Gitta 3 Lai, Mingjun 3 Lu, Xiliang 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, Xuemei 2 Choi, Bosu 2 Dan, Wei 2 Doostan, Alireza 2 Eftekhari, Armin 2 Fountoulakis, Kimon 2 Geng, Pengbo 2 Gondzio, Jacek 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, Qia 2 Lian, Feng 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 Qi, Houduo 2 Ruan, Guoqing 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 Xiang, Jianhong 2 Xu, Fengmin 2 Yin, Xiangjun 2 Yue, Huihui 2 Zhang, Na 2 Zhang, Xiaoqun 2 Zhu, Zhihui 1 Aberdam, Aviad 1 Abou-Kandil, Hisham 1 Aceska, Roza 1 Adalsteinsson, Gudmundur F. 1 Adamo, Alessandro 1 Ailon, Nir 1 Alabi, Tolu 1 Aldroubi, Akram 1 Ambat, Sooraj K. ...and 431 more Authors
all top 5

### Referenced in 100 Serials

 37 Applied and Computational Harmonic Analysis 13 Circuits, Systems, and Signal Processing 9 Science China. Mathematics 8 Mathematical Problems in Engineering 6 Inverse Problems 6 SIAM Journal on Imaging Sciences 5 Information Sciences 5 Journal of Machine Learning Research (JMLR) 5 Inverse Problems and Imaging 4 Journal of Computational Physics 4 Mathematics of Computation 4 Journal of Computational and Applied Mathematics 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 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 Journal of Mathematical Imaging and Vision 2 Computational Optimization and Applications 2 The Journal of Fourier Analysis and Applications 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 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 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 Mathematical Programming. Series A. Series B 1 International Journal of Bifurcation and Chaos in Applied Sciences and Engineering 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 Journal of Inequalities and Applications 1 Journal of Combinatorial Optimization 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 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 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 1 SIAM/ASA Journal on Uncertainty Quantification 1 Journal of Mathematical Modeling 1 AMM. Applied Mathematics and Mechanics. (English Edition) 1 Applied and Numerical Harmonic Analysis 1 Mathematical Foundations of Computing 1 Results in Applied Mathematics
all top 5

### Referenced in 24 Fields

 163 Information and communication theory, circuits (94-XX) 94 Numerical analysis (65-XX) 69 Operations research, mathematical programming (90-XX) 39 Computer science (68-XX) 32 Statistics (62-XX) 23 Linear and multilinear algebra; matrix theory (15-XX) 16 Harmonic analysis on Euclidean spaces (42-XX) 14 Approximations and expansions (41-XX) 14 Calculus of variations and optimal control; optimization (49-XX) 14 Probability theory and stochastic processes (60-XX) 8 Operator theory (47-XX) 6 Partial differential equations (35-XX) 5 Biology and other natural sciences (92-XX) 4 Dynamical systems and ergodic theory (37-XX) 3 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)