Analogs of compressed sensing 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 &lt; 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".)
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.