Analogs of compressed sensing

Question

In compressed sensing, the goal is to find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from the compression (the "sketch"). More formally, the standard setup is that there is a signal vector $x \in \mathbb{R}^n$ for which $\|x\|_0 < k$, and the compressed representation equals $Ax$ where $A$ is a $R$-by-$n$ real matrix where we want $R \ll n$. The magic of compressed sensing is that one can explicitly construct $A$ such that it allows fast (near-linear time) exact recovery of any $k$-sparse $x$ with $R$ as small as $O(k n^{o(1)})$. I might not have the parameters best known but this is the general idea.

My question is: are there similar phenomena in other settings? What I mean is that the input signal could come from some "low complexity family" according to a measure of complexity that is not necessarily sparsity. We then want compression and decompression algorithms, not necessarily linear maps, that are efficient and correct. Are such results known in a different context? What would your guess be for a more "general" theory of compressed sensing?

(Of course, in applications of compressed sensing, linearity and sparsity are important issues. The question I ask here is more "philosophical".)

Answer 1

Your question addresses the "exact" recovery problem (we want to recover a k-sparse $x$ exactly given $Ax$). In the following though I will focus on the "robust" version, where $x$ is an arbitrary vector and the goal of the recovery algorithm is to find a $k$-sparse approximation $x'$ to $x$ (this distinction actually matters for some of the discussion below). Formally you want to following problem (call it $P_1$):

Design $A$ such that for any $x$ one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $k$-sparse vectors.

Here, $\| \cdot \|_L$ and $\| \cdot \|_R$ denote the left and the right norm, and $C$ is the "approximation factor". There are various choices possible for $\| \cdot \|_L$ and $\| \cdot \|_R$. For concreteness, one can think that both are equal to $\ell_2$ or $\ell_1$; it can get more messy though.

Now to some of the analogs and generalizations.

Arbitrary basis. First, observe that any scheme satisfying the above definition can used to solve a more general problem, where the recovered signal $x'$ is sparse in an arbitrary basis (say, wavelet of Fourier), not just the standard one. Let $B$ be the basis matrix. Formally, a vector $u$ is $k$-sparse in basis $B$ if $u=Bv$ where $v$ is $k$-sparse. Now we can consider the generalized problem (call it $P_B$):

Design $A_B$ such that given $A_B x$, one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all vectors that are $k$-sparse in $B$.

One can reduce this problem to the earlier problem $P_1$ by changing the basis, i.e., using a measurement matrix $A_B = A B^{-1}$. If we have a solution to $P_1$ in the $\ell_2$ norm (i.e., the left and the right norms equal to $\ell_2$), we also get a solution to $P_B$ in the $\ell_2$ norm. If $P_1$ uses other norms, we solve $P_B$ in those norms modified by changing the basis.

One caveat in the above is that in the above approach, we need to know the matrix $B$ in order to define $A_B$. Perhaps surprisingly, if we allow randomization ($A_B$ is not fixed but instead chosen at random), it is possible to chose $A_B$ from the a fixed distribution that is independent from $B$. This is the so-called universality property.

Dictionaries. The next generalization can be obtained by dropping the requirement that $B$ is a basis. Instead, we can allow $B$ to have more rows than columns. Such matrices are called (overcomplete) dictionaries. One popular example is the identity matrix on top of the Fourier matrix. Another example is a matrix where the rows are the characteristic vectors of all intervals in {1 ... n}; in this case, the set { $Bu: \mbox{u is k-sparse}$} contains all "$k$-histograms", i.e., piecewise constant functions over {1 ... n} with at most $k$ pieces.

As far as I know there is no general theory for such arbitrary dictionaries, although there has been a fair amount of work on this topic. See e.g., Candes-Eldar-Needell'10 or Donoho-Elad-Temlyakov, IEEE Transactions on Information Theory, 2004.

Sketching for histograms was extensively investigated in streaming and database literature, e.g., Gilbert-Guha-Indyk-Kotidis-Muthukrishnan-Strauss, STOC 2002 or Thaper-Guha-Indyk-Koudas, SIGMOD 2002.

Models. (also mentioned by Arnab). A different generalization is to introduce restrictions on the sparsity patterns. Let $M$ be a subset of $k$-subsets of {1 ... n}. We say that $u$ is $M$-sparse if the support of $u$ is included in an element of $M$. We can now pose the problem (call it $P_M$):

Design $A$ such that for any $x$ one can recover $x'$ where $\|x-x'\|_L \le$

$\min_{x"} C \|x-x"\|_R$, where $x"$ ranges over all $M$-sparse vectors.

For example, the elements of $M$ could be of the form $I_1 \cup \ldots \cup I_k$, where each $I_i$ corresponds to one "sub-block"of {1 ... n} of some length $b$, i.e., $I_i$ is of the form { jb+1 ... (j+1)b} for some $j$. This is the so-called "block sparsity" model.

The benefits of models is that one can save on the number of measurements, compared to the generic $k$-sparsity approach. This is because the space of $M$-sparse signals is smaller than the space of all $k$-sparse signals, so the matrix $A$ needs to preserve less information. For more, see Baraniuk-Cevher-Duarte-Hegde, IEEE Transactions on Information Theory, 2010 or Eldar-Mishali, IEEE Transactions on Information Theory, 2009.

Hope this helps.

Answer 2

There is a generalization of compressed sensing to the non-commutative setting called matrix completion. In the exact setting, you are given an unknown $m \times n$ matrix $M$ which, instead of sparsity, is known to have low rank $r \ll m,n$. Your goal is to reconstruct the $r$ singular values and singular vectors of this matrix by sampling only $\tilde{O}(rm+rn)$ coefficients of the matrix, rather than $O(mn)$ as required in the worst case.

If the singular vectors are sufficiently "incoherent" (roughly, not too well aligned) with the basis in which you are sampling matrix elements, then you can succeed with high probability by solving a convex program, similar to standard compressed sensing. In this case, you have to minimize the Schatten 1-norm, i.e. the sum of the singular values.

This problem also has lots of applications, for example, to giving book recommendations to a customer of an online book store from knowing only the few ratings that other customers have generated. In this context, the rows and columns of $M$ are labeled by the books and the customers, respectively. The few visible matrix elements are the customer ratings of the books they previously bought. The matrix $M$ is expected to be low rank because we believe that typically only a few primary factors influence our preferences. By completing $M$, the vendor can make accurate predictions about which books you are likely to want.

A good start is this paper by Candés and Recht, Exact Matrix Completion via Convex Optimization. There is also a really cool generalization where you are allowed to sample in an arbitrary basis for the matrix space. This paper by David Gross, Recovering low-rank matrices from few coefficients in any basis uses this generalization to substantially simplify the proofs of matrix completion, and for some bases you can remove the incoherence assumption as well. That paper also contains the best bounds to date on the sampling complexity. It may sound strange to sample in an arbitrary basis, but it is actually quite natural in the setting of quantum mechanics, see for example this paper, Quantum state tomography via compressed sensing.

Answer 3

There is manifold-based compressed sensing, in which the sparsity condition is replaced by the condition that the data lie on a low-dimensional submanifold of the natural space of signals. Note that sparsity can be phrased as lying on a particular manifold (in fact, a secant variety).

See, for example this paper and the references in its introduction. (I admittedly do not know if this paper is representative of the area -- I am more familiar with the related topic of manifold-based classifiers a la Niyogi-Smale-Weinberger.)

Answer 4

I suppose that, at the level of generality in which I've posed the question, the paper "Compression of samplable sources" by Trevisan, Vadhan and Zuckerman (2004) also qualifies as one possible answer. They show that in many cases, if the source of input strings is of low complexity (e.g., samplable by logspace machines), then one can compress, and decompress, in polynomial time to length an additive constant away from the entropy of the source.

I don't really know though if compressed sensing can be put into some larger theory of compression.

Answer 5

One analog of compressive sensing is in machine learning when you try to estimate a high dimensional weight vector (e.g., in classification/regression) from a very small sample size. To deal with underdetermined systems of linear equations in such settings, one typically enforces sparsity (via l0 or l1 penalty) on the weight vector being learned. To see the connection, consider the following classification/regression problem from machine learning:

Represent the N examples of D dimensions each (D >> N) as an NxD matrix X. Represent the N responses (one for each example) as an Nx1 vector Y. The goal is to solve for a Dx1 vector theta via the following equation: Y = X*theta

Now here is the analogy of this problem to compressive sensing (CS): you want to estimate/measure theta which is a D dimensional vector (akin to an unknown "signal" in CS). To estimate this, you use a matrix X (akin to the design matrix in CS) and N 1-D measurements Y (akin to the compressed signal in CS, since D >> N).

Answer 6

See: http://www.damtp.cam.ac.uk/user/na/people/Anders/Inf_CS43.pdf