Using FFT in CVX

1

I am using CVX to solve the following problem:

cvx_begin quiet
  variable x(l)
  minimize( norm(x, 1) )
  subject to
    y == D * x;
cvx_end

In the scenario I am working on, the matrix D has a very particular structure since it is built from a partial Fourier matrix and the identity matrix, that is D = [F I], where F is a “fat” Fourier matrix of size n x m and I is the identity matrix of size n x n. I would like to avoid having to build the matrix D, since I am working with large values of n and m. Because of the particular structure of D the constraint can also be written in terms of the Fourier transform of a section of x. I have been able to replace D computing the Fourier transform making use of “polyval” as follows:

l = m + n;
w = exp(1i * 2 * pi / m * (0:(n-1))');

cvx_begin quiet

  variable x(l) complex

  expression xft(n)
  xft(1) = sum(x(1:m)) / sqrt(m);
  for k = 2 : n
    xft(k) = polyval(x(m:-1:1), w(k)) / sqrt(m);
  end

  minimize( norm(x, 1) )
  subject to
    y == xft + x(m+1:end);
cvx_end

This option works fine and leads to exactly the same solution. I would like to use the Matlab implementation of “fft” in order to speed up the computation of the Fourier transform. Is there an easy way of using it in CVX? I have checked the section “Adding new functions to the atom library” in the tutorial, but haven’t been able to obtain a working version. This is what I have tried (I’ve added this function in a subfolder @cvx):

function y = my_ifft(x)
y = cvx( x.size_, sparse(ifft(full(x.basis_))) );
end

And then I have used this function to compute the constraint. But doesn’t seem to be working… Any suggestions?

2

Sorry, this cannot be done. CVX is built under the assumption that it has the full basis of any linear operations it performs. The solvers also make that assumption.

3

Thanks for the quick reply. I’ll let you know if I manage to speed this up in some other way.

4

Honestly, the solution is not to use CVX. CVX is designed for convenience, not speed. And the underlying algorithms favor accuracy and reliability over speed and memory consumption.

Compressed sensing problems and other models like yours are generally solved with first-order methods these days, using software that takes advantage of the linear operator structure like the FFT. In fact, you may want to try my other tool TFOCS. It is not as easy to use, of course.