sparse estimation / compressed sensing linear system solver

finds a sparse solution x to the under-determined system Ax=y, that has at most 2 non-zero elements

sparse_sensing12 - is the function code
sparse_sensing_example - shows how to use it.
x = sparse_sensing12( A,y,epsE )
Written by Prof. Yoash Levron,
Electrical Engineering, Technion, Israel, September 2014.

This function solves the under-determined system of equations Ax=y, with a matrix A that has less rows than columns. The function locates the solution vector x which is "the most sparse", that is, the solution vector that has the fewest number of non-zero elements. If a sparse solution exists the function is guaranteed to locate it.

function inputs:
A - the sensing matrix (dimensions M x N, where M<N)
y - the known output vector (vector of known measurements,(dimensions M x 1)
epsE - tolerable error of solution. If the solution vector x generates an error with a second norm larger than epsE, the function throws an error message.

function output:
x - the sparse vector that is estimated (dimensions N x 1).
It is assumed that x has at most 2 non-zero elements.

This version of the code solves for x only if it has 1 or 2 non-zero elements, and it does so by scanning all possible support bases for the vector x. (that is, it scans every possible combination of one or two column vectors from A). If there is no sparse solution x (with one or two elements), the function will generate an error, Although a solution vector x with more than two non-zero elements may exist. (this can be easily checked by typing x = A\y in the Matlab command window). Because of this exhaustive scan, if a solution exists, the function is guaranteed to locate it, and further more, the function will locate the sparse solution for which the second norm of the error is minimal.

Conditions on the matrix A:
The function will locate a sparse solution, if it exists. However, in general, this solution may not be unique, that is, other sparse solutions to the system of equations Ax=y may exist. A sufficient condition for the solution to be unique is that every combination of M columns from the matrix A is linearly independent, where M is the number of rows in A. (The general theorem is given by a condition on the 'spark' of the matrix A).

Complexity limit:
The complexity of computation is determined primarily by the number of columns in A. The function can handle a matrix with 500 columns and more on a standard PC.