2009/07/21 by Mihailo Stojnic, Stojnic, Mihailo
Engineering · Physics and Astronomy · #FOS: Computer and information sciences #Information Theory (cs.IT) #Photoacoustic and Ultrasonic Imaging #Random lasers and scattering media #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.0907.3679
openalex publication_date 2009/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the most basic problems in compressed sensing is solving an under-determined system of linear equations. Although this problem seems rather hard certain ℓ1-optimization algorithm appears to be very successful in solving it. The recent work of \citeCRT,DonohoPol rigorously proved (in a large dimensional and statistical context) that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that ℓ1-optimization algorithm succeeds in solving the system. In more recent papers \citeStojnicICASSP09block,StojnicJSTSP09 we considered the setup of the so-called block-sparse unknown vectors. In a large dimensional and statistical context, we determined sharp lower bounds on the values of allowable sparsity for any given number (proportional to the length of the unknown vector) of equations such that an ℓ2/ℓ1-optimization algorithm succeeds in solving the system. The results established in \citeStojnicICASSP09block,StojnicJSTSP09 assumed a fairly large block-length of the block-sparse vectors. In this paper we consider the block-length to be a parameter of the system. Consequently, we then establish sharp lower bounds on the values of the allowable block-sparsity as functions of the block-length.