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

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 -