Compressed sensing and matrix completion: exploiting simplicity in data

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. Compressed sensing and matrix completion

show that this simplicity in the data can be exploited to reduce the

number of measurements. For instance, if a vector of length $N$

can be represented exactly using $k$ terms of a known basis

then $2k\log(N/k)$ measurements is typically sufficient to recover

the vector exactly. This can result in dramatic time savings when

k