Computer Science – Information Theory
Scientific paper
2010-01-28
Computer Science
Information Theory
Accepted to be presented at the IEEE International Symposium on Information Theory (ISIT 2010). 5 pages, 2 Figures. Minor edit
Scientific paper
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\times 512$ matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.
Chertkov Michael
Chilappagari Shashi Kiran
Vasic Bane
No associations
LandOfFree
Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Worst Configurations (Instantons) for Compressed Sensing over Reals: a Channel Coding Approach will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-254272