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.