Artificial Intelligence Events
"How Many Random Projections Does One Need to Recover a $k$-sparse Vector?" - Jared Tanner - U of Edinburgh - 4-5pm
Location: CS1.01
Abstract:
The essential information contained in most large data sets is
small when compared to the size of the data set. That is, the
data can be well approximated using relatively few terms in a
suitable transformation. This paradigm of Compressed Sensing
suggests a revolution in how information is collected and processed.
In this talk we consider a stronger notion of compressibility,
sparsity, which measures the number of non-zero entries. For
data sets which are sparse (possibly following a transformation),
the data can often be recovered efficiently, with relatively few
randomized measurements by utilizing highly non-linear optimization
based reconstruction techniques.
Specifically, consider an underdetermined system of linear
equations $y=Ax$ with known y and $n\times N$, matrix A with
$n<N$. We seek the sparsest solution, i.e., the x with fewest
nonzeros satisfying $y=Ax$. In general this problem is NP-hard.
However, for many matrices $A$ there is a threshold phenomenon:
if the sparsest solution is sufficiently sparse, it can be found
by linear programming. Quantitative values for a strong and weak
threshold will be presented. The strong threshold guarantees
the recovery of the sparsest solution $x_o$, whereas a weaker
sparsity constraint ensures the recovery of the sparsest solution
for most $x_o$. Connections with high-dimensional geometry
imply results about the structure of Gaussian point clouds and
the neighborliness of polytopes.
The essential information contained in most large data sets is
small when compared to the size of the data set. That is, the
data can be well approximated using relatively few terms in a
suitable transformation. This paradigm of Compressed Sensing
suggests a revolution in how information is collected and processed.
In this talk we consider a stronger notion of compressibility,
sparsity, which measures the number of non-zero entries. For
data sets which are sparse (possibly following a transformation),
the data can often be recovered efficiently, with relatively few
randomized measurements by utilizing highly non-linear optimization
based reconstruction techniques.
Specifically, consider an underdetermined system of linear
equations $y=Ax$ with known y and $n\times N$, matrix A with
$n<N$. We seek the sparsest solution, i.e., the x with fewest
nonzeros satisfying $y=Ax$. In general this problem is NP-hard.
However, for many matrices $A$ there is a threshold phenomenon:
if the sparsest solution is sufficiently sparse, it can be found
by linear programming. Quantitative values for a strong and weak
threshold will be presented. The strong threshold guarantees
the recovery of the sparsest solution $x_o$, whereas a weaker
sparsity constraint ensures the recovery of the sparsest solution
for most $x_o$. Connections with high-dimensional geometry
imply results about the structure of Gaussian point clouds and
the neighborliness of polytopes.