Name
Title | ||
|---|---|---|
Recovery of a Sparse Integer Solution to an Underdetermined System of Linear Equations |
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2011 | CoRR | Integer,Discrete mathematics,Linear equation,Mathematical optimization,Combinatorics,Normal distribution,Underdetermined system,Matrix (mathematics),Binary entropy function,Linear programming relaxation,Mathematics,Compressed sensing |
DocType | Volume | Citations |
Journal | abs/1112.1757 | 2 |
PageRank | References | Authors |
0.51 | 5 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| T. S. Jayram | 1 | 1373 | 75.87 |
| Soumitra Pal | 2 | 16 | 3.84 |
| Vijay Arya | 3 | 541 | 41.32 |