1
$\begingroup$

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.

Question:

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ This is brand new research. I strongly suggest you contact the authors. But frankly I suspect that the "constraint" on $\lambda_c$ isn't really a constraint, it is a sufficient condition. Thus sometimes, the algorithm will succeed even if it is violated---but there are no guarantees. $\endgroup$
    – Michael Grant
    Apr 8, 2013 at 2:48
  • $\begingroup$ I should add that I am quite certain that adding a cardinality constraint will not be possible. It wouldn't simply make the problem non-convex and NP-hard---the number of potential spikes is uncountable. $\endgroup$
    – Michael Grant
    Apr 8, 2013 at 4:51
  • $\begingroup$ @MichaelGrant thanks for your comments. I've updated the question to change 'constraint' to condition. I was thinking along the lines of if there was only one 'best' spike where would it be located, but I imagine it would be pretty easy to show that it would be where the maximum is. Just a clarification, with the cardinality constraint most likely not being possible, is that for both linear program and SDP, or just SDP? Thanks again. $\endgroup$
    – geometrikal
    Apr 8, 2013 at 6:19
  • 1
    $\begingroup$ Yes, both. The very reason these kinds of papers are written is because the true NP-hard cardinality minimziation is intractable. $\endgroup$
    – Michael Grant
    Apr 9, 2013 at 1:12

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.