I'm currently learning about using linear and semidefinite programming to find sparse solutions to problems. In particular, finding sparse solutions where the sampling functions are sinusoidal (Dirichlet kernel).
I've implemented a linear programming solution with a discrete approximation using
l1magic MATLAB library, and an SDP solution based on the MATLAB example in the paper "Towards a mathematical theory of super-resolution" someone suggested in a previous question.
The CVX code is:
cvx_solver sdpt3 cvx_begin sdp variable X(n+1,n+1) hermitian; X >= 0; X(n+1,n+1) == 1; trace(X) == 2; for j = 1:n-1, sum(diag(X,j)) == X(n+1-j,n+1); end maximize(real(X(1:n,n+1)'*y)) cvx_end
In the above paper, if the minimum distance between spikes is greater than or equal to $2 \lambda_c$, where $\lambda_c$ is the wavelength of the cutoff frequency, this condition is sufficient to guarantee the solution is unique and can be obtained to infinite precision (page 5).
I've noticed that if all the spikes are the same sign then shorter distances still give me the correct result. If they are different signs then the above condition seems to apply.
Is there a way to introduce either a
- cardinality constraint, where the number of spikes is known, or
- sign constraint, where the signs of the spikes are known
that can give a solution where the minimum distance condition is not met?