TY - GEN
T1 - Worst configurations (Instantons) for compressed sensing over reals
T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010
AU - Chilappagari, Shashi Kiran
AU - Chertkov, Michael
AU - Vasic, Bane
PY - 2010
Y1 - 2010
N2 - We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated 120 × 512 matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.
AB - We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated 120 × 512 matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.
UR - http://www.scopus.com/inward/record.url?scp=77955699057&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77955699057&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2010.5513360
DO - 10.1109/ISIT.2010.5513360
M3 - Conference contribution
AN - SCOPUS:77955699057
SN - 9781424469604
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 1978
EP - 1982
BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Y2 - 13 June 2010 through 18 June 2010
ER -