Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

4 pages, contributed paper to be published at NIPS 2011 Workshop on Sparse Representation and Low-rank Approximation, 16 Decem

Scientific paper

We consider a system of m linear equations in n variables Ax=b where A is a given m x n matrix and b is a given m-vector known to be equal to Ax' for some unknown solution x' that is integer and k-sparse: x' in {0,1}^n and exactly k entries of x' are 1. We give necessary and sufficient conditions for recovering the solution x exactly using an LP relaxation that minimizes l1 norm of x. When A is drawn from a distribution that has exchangeable columns, we show an interesting connection between the recovery probability and a well known problem in geometry, namely the k-set problem. To the best of our knowledge, this connection appears to be new in the compressive sensing literature. We empirically show that for large n if the elements of A are drawn i.i.d. from the normal distribution then the performance of the recovery LP exhibits a phase transition, i.e., for each k there exists a value m' of m such that the recovery always succeeds if m > m' and always fails if m < m'. Using the empirical data we conjecture that m' = nH(k/n)/2 where H(x) = -(x)log_2(x) - (1-x)log_2(1-x) is the binary entropy function.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations 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 Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-547393

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.