The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.
Decoding by Linear Programming
Open accessAbstract
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Cited by
An Introduction To Compressive Sampling
Candes, E. J., & Wakin, M. B. (2008) · IEEE Signal Processing Magazine · doi:10.1109/msp.2007.914731 · Cited by 10,017
Stable signal recovery from incomplete and inaccurate measurements
Candès, E. J., Romberg, J. K., & Tao, T. (2006) · Communications on Pure and Applied Mathematics · doi:10.1002/cpa.20124 · Cited by 7,036
Self-citation(2011) · Cited by 6,993
(2015) · Cited by 2,857
Exact Reconstruction of Sparse Signals via Nonconvex Minimization
Chartrand, R. (2007) · IEEE Signal Processing Letters · doi:10.1109/lsp.2007.898300 · Cited by 1,277
Iteratively reweighted algorithms for compressive sensing
Chartrand, R., & Yin, W. (2008) · 2008 IEEE International Conference on Acoustics, Speech and Signal Processing · doi:10.1109/icassp.2008.4518498 · Cited by 1,248
Sparse, Dense, and Attentional Representations for Text Retrieval
Luan, Y., Eisenstein, J., Toutanova, K., & Collins, M. (2021) · Transactions of the Association for Computational Linguistics · doi:10.1162/tacl_a_00369 · Cited by 363
Non-convex Optimization for Machine Learning
Jain, P., & Kar, P. (2017) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000058 · Cited by 364
Secure Control Systems: A Quantitative Risk Management Approach
(2015) · IEEE Control Systems · doi:10.1109/mcs.2014.2364709 · Cited by 316
Kang, H., Zhang, A., Cai, T. T., & Small, D. S. (2016) · Journal of the American Statistical Association · doi:10.1080/01621459.2014.994705 · Cited by 265
DC formulations and algorithms for sparse optimization problems
Gotoh, J.-Y., Takeda, A., & Tono, K. (2018) · Mathematical Programming · doi:10.1007/s10107-017-1181-0 · Cited by 184
Theory and applications of robust optimization
Bertsimas, D., Brown, D. B., & Caramanis, C. (2011) · SIAM Review · doi:10.1137/080734510 · Cited by 134
Efficient Generation of Transcriptomic Profiles by Random Composite Measurements
Cleary, B., Cong, L., Cheung, A., Lander, E. S., & Regev, A. (2017) · Cell · doi:10.1016/j.cell.2017.10.023 · Cited by 114
Learning to Hash With Optimized Anchor Embedding for Scalable Retrieval
Guo, Y., Ding, G., Liu, L., Han, J., & Shao, L. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2652730 · Cited by 108
Optimal siting and sizing of distribution system operator owned ev parking lots
Kazemi, M. A., Sedighizadeh, M., Mirzaei, M. J., & Homaee, O. (2016) · Applied Energy · doi:10.1016/j.apenergy.2016.06.125 · Cited by 100
Reconstructing cortical current density by exploring sparseness in the transform domain
Ding, L. (2009) · Physics in Medicine and Biology · doi:10.1088/0031-9155/54/9/006 · Cited by 99
Damage Identification Scheme Based on Compressive Sensing
Wang, Y., & Hao, H. (2015) · Journal of Computing in Civil Engineering · doi:10.1061/(asce)cp.1943-5487.0000324 · Cited by 77
Space–time event sparse penalization for magneto-/electroencephalography
Bolstad, A., Veen, B. V., & Nowak, R. (2009) · NeuroImage · doi:10.1016/j.neuroimage.2009.01.056 · Cited by 71
Sparse Group Lasso: Consistency and Climate Applications
Chatterjee, S., Steinhaeuser, K., Banerjee, A., Chatterjee, S., & Ganguly, A. (2012) · Proceedings of the 2012 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972825.5 · Cited by 72
Compressive Sequential Learning for Action Similarity Labeling
Qin, J., Liu, L., Zhang, Z., Wang, Y., & Shao, L. (2016) · IEEE Transactions on Image Processing · doi:10.1109/tip.2015.2508600 · Cited by 55
Elhage, N., Hume, T., Olsson, C., Schiefer, N., Henighan, T., Kravec, S., Hatfield-Dodds, Z., Lasenby, R., Drain, D., Chen, C., et al. (2022) · arXiv · doi:10.48550/arxiv.2209.10652 · Cited by 51
Yu, Y., Han, F., Bao, Y., & Ou, J. (2016) · IEEE Sensors Journal · doi:10.1109/jsen.2015.2512846 · Cited by 48
Emerging data technology in structural health monitoring: compressive sensing technology
Bao, Y., Li, H., & Ou, J. (2014) · Journal of Civil Structural Health Monitoring · doi:10.1007/s13349-013-0064-1 · Cited by 43
Nonconvex Demixing From Bilinear Measurements
Dong, J., & Shi, Y. (2018) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2018.2864660 · Cited by 37
Sparsity-Aware Learning and Compressed Sensing: An Overview
Theodoridis, S., Kopsinis, Y., & Slavakis, K. (2014) · Academic Press Library in Signal Processing · doi:10.1016/b978-0-12-396502-8.00023-1 · Cited by 14
Recent Advances in Hyperspectral Unmixing Using Sparse Techniques and Deep Learning
Zhang, S., Su, Y., Xu, X., Li, J., Deng, C., & Plaza, A. (2020) · Advances in Computer Vision and Pattern Recognition · doi:10.1007/978-3-030-38617-7_13 · Cited by 8
GA Based Estimation of Sparse MIMO Channels with Superimposed Training
Mansoor, B., Nawaz, S. J., Tiwana, M. I., Ahmed, J., & Haseeb, A. (2018) · Elektronika ir Elektrotechnika · doi:10.5755/j01.eie.24.6.22294 · Cited by 3
Metadata
- Authors
- Candes, E. J., & Tao, T.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2005-12
- Volume
- 51
- Issue
- 12
- Pages
- 4203-4215
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2129131372
- Cited by
- 7,121
- References
- 1
- FWCI
- 82.34
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
