Metadata
Abstract:
Suppose we are given a vector f in a class {\cal F} \subset{\BBR}^N, e.g., a class of digital signals or digital images. How many linear measurements do we need to make about f to be able to recover f to within precision \epsilon in the Euclidean (\ell_2) metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct f to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the nth largest entry of the vector \vert f\vert (or of its coefficients in a fixed basis) obeys \vert f\vert _{(n)} \le R \cdot n^{-1/p}, where R > 0 and p > 0. Suppose that we take measurements y_k = \langle f, X_k\rangle, k = 1, \ldots, K , where the X_k are N-dimensional Gaussian vectors with independent standard normal entries. Then for each...
Published in: IEEE Transactions on Information Theory ( Volume: 52, Issue: 12, December 2006)
Citations are not available for this document.
Cites in Papers - |
Cites in Papers - IEEE (2352)
Select All
1.
Junjie Tong, Shenwei Shou, Hui Wang, "A Dictionary-Enhanced Clustering Compressive Sensing Routing Protocol for Large-Scale WSNs", IEEE Sensors Journal, vol.25, no.4, pp.7445-7456, 2025.
2.
Tianyu Zhang, Kuntao Ye, Yue Zhang, Rui Lu, "Multi-Scale Channel Distillation Network for Image Compressive Sensing", IEEE Access, vol.13, pp.9524-9537, 2025.
3.
Jeong-Il Byeon, Wookyung Lee, Jihoon Choi, "Compressive SAR Imaging Based on Modified Low-Rank and Sparse Decomposition", IEEE Access, vol.13, pp.1663-1679, 2025.
4.
Shaoquan Zhang, Jiajun Zheng, Pengfei Lai, Fan Li, Lianhui Liang, Antonio Plaza, Chengzhi Deng, Shengqian Wang, "Sparse Unmixing of Hyperspectral Images With Noise Reduction Using Spatial Filtering", IEEE Transactions on Instrumentation and Measurement, vol.74, pp.1-18, 2025.
5.
Rongpei Zhou, Rongfa Li, Yaqian Wu, Jie Chen, Jin Hong, Lisu Yu, Qiegen Liu, Yudong Zhang, "Semi-Tensor Product Compressed Sensing With Its Applications: A Review", IEEE Sensors Journal, vol.25, no.3, pp.4096-4114, 2025.
6.
Nicolò Bellarmino, Riccardo Cantoro, Sophie M. Fosson, Martin Huch, Tobias Kilian, Ulf Schlichtmann, Giovanni Squillero, "COSMO: COmpressed Sensing for Models and Logging Optimization in MCU Performance Screening", IEEE Transactions on Computers, vol.74, no.2, pp.652-664, 2025.
7.
Mohammad Mahdi Omati, Seyed Mohammad Karbasi, Arash Amini, "Elevating ISAR Imaging Resolution via 2-D SLIM", IEEE Sensors Journal, vol.25, no.1, pp.940-950, 2025.
8.
Xiaoqian Huang, Yong Gong, Wenhao Wu, Saike Zhu, Yi Zhao, "CSDet: A Compressed Sensing Object Detection Architecture With Lightweight Networks", IEEE Transactions on Circuits and Systems for Video Technology, vol.35, no.3, pp.2355-2368, 2025.
9.
Yuhan Wang, Jian Zhao, Zhen Wang, Kaiwen Zhu, Zehua Dong, Zegang Ding, "UAV-SAR Panoramic 3D Imaging for Urban Area: A Multi-angle Tomography Approach", 2024 IEEE International Conference on Signal, Information and Data Processing (ICSIDP), pp.1-5, 2024.
10.
Penggen Zheng, Xuanhui Li, Jiayi Yan, Wei Wang, Ying Zhou, "A Convolutional Neural Network Using Multi-Level Feature Projection for SAR Vehicle Recognition", 2024 IEEE International Conference on Signal, Information and Data Processing (ICSIDP), pp.1-5, 2024.
11.
C.G. Parini, S.F. Gregson, "Recent Advances in Compressive Sensing for Production Test and Antenna Diagnostics of 5G Massive MIMO Antennas", 2024 Antenna Measurement Techniques Association Symposium (AMTA), pp.1-6, 2024.
12.
Yuning Qi, Jingguo Bi, Haipeng Peng, Lixiang Li, "Efficient Homomorphic Encryption for Multikey Compressed Sensing in Lightweight Cloud-Based Image Processing", IEEE Sensors Journal, vol.24, no.24, pp.41365-41377, 2024.
13.
Guillaume Perez, Laurent Condat, Michel Barlaud, "Near-Linear Time Projection onto the $\ell_{1,\infty}$ Ball; Application to Sparse Neural Networks", 2024 IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI), pp.335-343, 2024.
14.
Ziqi Wang, Zihan Cao, Julan Xie, Huiyong Li, Zishu He, "Towards Applicable Unsupervised Signal Denoising via Subsequence Splitting and Blind Spot Network", IEEE Transactions on Signal Processing, vol.72, pp.4967-4982, 2024.
15.
Mohammad-Reza Seidi, Armin Karimi, Joachim Oberhammer, "A Novel Frequency-Sweeping Scanning Notch Beam Radar at 238-248 GHz", 2024 21st European Radar Conference (EuRAD), pp.95-98, 2024.
16.
Alvaro Lopez Paredes, Felipe Gutierrez-Barragan, Miguel Heredia Conde, "Coherence, Distance and Error: Understanding Coded Demodulation in PB-ToF Imaging", 2024 International Workshop on the Theory of Computational Sensing and its Applications to Radar, Multimodal Sensing and Imaging (CoSeRa), pp.112-116, 2024.
17.
Yanjun Yan, Chuanrong Liu, Yijiu Zhao, Houjun Wang, Lei Qian, Kai Chen, Yifan Wang, "A Lower-Correlation Random Demodulator Architecture Using Random Sampling Period Zeroing Integration Method", 2024 32nd European Signal Processing Conference (EUSIPCO), pp.2702-2706, 2024.
18.
Yanjun Yan, Chuanrong Liu, Yijiu Zhao, Houjun Wang, Lei Qian, Kai Chen, Yifan Wang, "A Lower-Correlation Random Demodulator Architecture Using Random Sampling Period Zeroing Integration Method", 2024 32nd European Signal Processing Conference (EUSIPCO), pp.2702-2706, 2024.
19.
Tadashi Wadayama, Ayano Nakai-Kasai, "Continuous-Time Sparse Signal Recovery", IEEE Access, vol.12, pp.118141-118153, 2024.
20.
Ya-Feng Liu, Tsung-Hui Chang, Mingyi Hong, Zheyu Wu, Anthony Man-Cho So, Eduard A. Jorswieck, Wei Yu, "A Survey of Recent Advances in Optimization Methods for Wireless Communications", IEEE Journal on Selected Areas in Communications, vol.42, no.11, pp.2992-3031, 2024.
21.
Xin Zou, Mingming Xu, Shanwei Liu, Hui Sheng, "Superpixel-Based Graph Laplacian Regularized and Weighted Robust Sparse Unmixing", IEEE Transactions on Geoscience and Remote Sensing, vol.62, pp.1-15, 2024.
22.
Jianbin Zheng, Yun Long, Feng Sun, Jun Lin, "Three-Dimensional Curvelet-Based WPOCS Reconstruction, Doppler-Shift Correction, and Noise Attenuation of Jittered Sampled Marine Vibrator Data", IEEE Transactions on Geoscience and Remote Sensing, vol.62, pp.1-17, 2024.
23.
Oluwole John Famoriji, Thokozani Shongwe, "Diagnosis of Antenna Array with Undefined Mutual Coupling via Optimization", 2024 International Conference on Electrical, Computer and Energy Technologies (ICECET, pp.1-5, 2024.
24.
Hongyu Zhao, Le Yang, Ge Wang, Ruiming Wang, "Research on Voice Compression Coding Scheme for Ground Penetrating Wireless Communication Based on Compressive Sensing", 2024 7th International Conference on Computer Information Science and Application Technology (CISAT), pp.778-781, 2024.
25.
Xiaolong Cheng, Li Guo, "Collaborative Optimization Unfolding Networks: Prior Compensation and Proximal Mapping Augmentation for Image Compressive Sensing", 2024 2nd International Conference on Algorithm, Image Processing and Machine Vision (AIPMV), pp.142-147, 2024.
26.
George Vershinin, Asaf Cohen, Omer Gurewitz, "Novel Bounds for Semi-Blind Multiple-Access in Massive MIMO", 2024 IEEE International Symposium on Information Theory (ISIT), pp.2157-2162, 2024.
27.
Yufan Fan, Marius Pesavento, "Tail-STELA for Fast Signal Recovery via Basis Pursuit", 2024 IEEE 13rd Sensor Array and Multichannel Signal Processing Workshop (SAM), pp.1-5, 2024.
28.
Surendra Singh, Shubham Tripathi, Tanya Jain, Saurabh Rana, Neelam Choudhary, "An Efficient and Privacy-Preserving Medical Image Compression and Sharing Protocol", 2024 15th International Conference on Computing Communication and Networking Technologies (ICCCNT), pp.1-7, 2024.
29.
Mudassir Masood, "Distributed Bayesian Sparse Signal Recovery Algorithm with Minimal Communication Load in Networks", 2024 IEEE 99th Vehicular Technology Conference (VTC2024-Spring), pp.1-5, 2024.
30.
Yuhua Yin, Zhiliang Liu, Qiang Zhang, Yong Qin, Mingjian Zuo, "A Data Compression Method With an Encryption Feature for Safe and Lightweight Vibration Condition Monitoring", IEEE Internet of Things Journal, vol.11, no.19, pp.30524-30535, 2024.
Cites in Papers - Other Publishers (2634)
1.
Peng Zhang, Zhuo Wang, Dan He, Danhong Huang, Haobo Li, Lin Du, Xiaofeng Sun, "Mode Analysis for the Rotating Aerodynamic Disturbance of a Transonic Fan", Journal of Turbomachinery, vol.147, no.5, 2025.
2.
Yuki Kato, "HIGH-RESOLUTION VISUALIZATION MEASUREMENT OF VORTEX-SHEDDING AT HIGH FREQUENCIES USING SUB-NYQUIST-RATE PIV AND COMPRESSED SENSING", Journal of Flow Visualization and Image Processing, vol.32, no.1, pp.81, 2025.
3.
Huadong Guo, Xinwu Li, Wenxue Fu, "Earth observation via tomographic synthetic aperture radar", New-Generation SAR for Earth Environment Observation, pp.193, 2025.
4.
Shan Yang, Zhirong Gao, Jingbo Guo, "A New Compressed Data Acquisition Method for Power System Based on Chaotic Compressive Measurement", Sensors, vol.24, no.23, pp.7499, 2024.
5.
Li-Yu Yu, Sixian You, "High-fidelity and high-speed wavefront shaping by leveraging complex media", Science Advances, vol.10, no.27, 2024.
6.
Yi Yang, Hongwei Ma, "A data assimilation pressure field measurement method for linear turbine cascades based on compressed sensing", Physics of Fluids, vol.36, no.11, 2024.
7.
Shuai Bian, Shouliang Qi, Chen Li, Yudong Yao, Yueyang Teng, "NL-CS Net: Deep Learning with Non-local Prior for Image Compressive Sensing", Circuits, Systems, and Signal Processing, 2024.
8.
Jun Wang, Qiang Ma, "On the implementation of ADMM with dynamically configurable parameter for the separable $$\\\\ell _{1}/\\\\ell _{2}$$ minimization", Optimization Letters, 2024.
9.
Yingming Lai, Jinyang Liang, "Encoders for Optical Imaging", Coded Optical Imaging, pp.15, 2024.
10.
Ming-Jie Sun, "Single-Pixel Imaging and Computational Ghost Imaging", Coded Optical Imaging, pp.131, 2024.
11.
Chané Moodley, Andrew Forbes, "Advances in Quantum Imaging with Machine Intelligence", Laser & Photonics Reviews, 2024.
12.
Xiao Hua Zhang, Xing Yong Xiao, Ze Peng Yang, Sheng En Fang, "Response reconstruction based on measurement matrix optimization in compressed sensing for structural health monitoring", Advances in Structural Engineering, 2024.
13.
Guillaume Lecué, Zong Shang, "A geometrical viewpoint on the benign overfitting property of the minimum $$\\\\ell _2$$-norm interpolant estimator and its universality", Probability Theory and Related Fields, 2024.
14.
Jongchan Park, Liang Gao, "Cascaded compressed-sensing single-pixel camera for high-dimensional optical imaging", PhotoniX, vol.5, no.1, 2024.
15.
Yang Liu, Gregory W. Wornell, William T. Freeman, Frédo Durand, "Imaging privacy threats from an ambient light sensor", Science Advances, vol.10, no.2, 2024.
16.
Quan Huang, Shaopeng Wei, Lei Zhang, "Interpretable ADMM-CSNet for interrupted sampling repeater jamming suppression", Digital Signal Processing, pp.104850, 2024.
17.
Yiming Liu , Yanwei Pang , Xuebin Sun , Yonghong Hou , Zhenghan Yang , Zhenchang Wang , " Dual states based reinforcement learning for fast MR scan and image reconstruction ", Neurocomputing , vol. 568 , pp. 127067 , 2024 .
18.
Zhuo Li, Ping Xu, Yuewei Jia, Ke-nan Chen, Bin Luo, Lingyun Xue, "A novel recursive sub-tensor hyperspectral compressive sensing of plant leaves based on multiple arbitrary-shape regions of interest", PeerJ Computer Science, vol.10, pp.e2410, 2024.
19.
Zheng Guan, Yu Wang, "Fusion of three-dimensional geotechnical and geophysical data for developing digital twin of underground space", Soils and Foundations, vol.64, no.6, pp.101528, 2024.
20.
Holger Boche, Adalbert Fono, Gitta Kutyniok, "Inverse Problems are Solvable on Real Number Signal Processing Hardware", Applied and Computational Harmonic Analysis, pp.101719, 2024.
21.
Ehsan Mostafapour, Changiz Ghobadi, Javad Nourinia, Ramin Borjali Navesi, "One‐Bit Distributed Sparse Spectrum Sensing Based on the DQA‐ZA‐LMS and DQA‐RZA‐LMS Algorithms Over Adaptive Networks", IET Signal Processing, vol.2024, no.1, 2024.
22.
Susumu Yamada, Masahiko Machida, Naoki Tanimura, "Selection method for observation points using Bayesian LASSO at estimating radiation source distribution from air dose rates", EPJ Web of Conferences, vol.302, pp.16004, 2024.
23.
A M Zheltikov, "The poisson property of extreme events in optics", Physica Scripta, vol.99, no.11, pp.115527, 2024.
24.
Iga Pawelec, Paul Sava, "High dynamic range land wavefield reconstruction from randomized acquisition", GEOPHYSICS, vol.89, no.6, pp.V563, 2024.
25.
Hongyan Wang, Yanping Bai, Jing Ren, Peng Wang, Ting Xu, Wendong Zhang, Guojun Zhang, "DOA Estimation Method for Vector Hydrophones Based on Sparse Bayesian Learning", Sensors, vol.24, no.19, pp.6439, 2024.
26.
Menglin Ye, Shidong Li, Cheng Cheng, Jun Xian, "Analyses of the tail-ℓ2 minimization for fast and enhanced sparse selections", Signal Processing, pp.109728, 2024.
27.
Kun-Kai Wen, Jia-Xin He, Peng Li, "Sparse recovery using expanders via hard thresholding algorithm", Signal Processing, pp.109715, 2024.
28.
Daniel L. Crane, Ruslan L. Davidchack, Alexander N. Gorban, "Minimal cover of high-dimensional chaotic attractors by embedded recurrent patterns", Communications in Nonlinear Science and Numerical Simulation, pp.108345, 2024.
29.
Xinxin Xiang, Fenghua Tong, Dawei Zhao, Xin Li, Shumian Yang, "Dual-domain sampling and feature-domain optimization network for image compressive sensing", Engineering Applications of Artificial Intelligence, vol.137, pp.109099, 2024.
30.
Chunyu You, Xing Li, Yuhang Hu, Ningge Huang, Yang Wang, Binmin Wu, Guobang Jiang, Jiayuan Huang, Ziyu Zhang, Bingxin Chen, Yue Wu, Junhan Liu, Xiangzhong Chen, Enming Song, Jizhai Cui, Peng Zhou, Zengfeng Di, Zhenghua An, Gaoshan Huang, Yongfeng Mei, "CMOS-compatible reconstructive spectrometers with self-referencing integrated Fabry–Perot resonators", Proceedings of the National Academy of Sciences, vol.121, no.33, 2024.
