Hankel nuclear norm

1

Hello there, I am quite new to cvx and i though to ask for a problem I have. I try to solve the following problem

min ||Ax-b||2 +lambda*||H(x)||* where H(x) denotes the Hankel matrix of the vector x and * the nuclear norm and lambda is the penalty term. I used the following code which worked well

cvx_begin quiet

  variable x(N,1)
  expression H((N+1)/2,(N+1)/2)
  for i = 1:N
      if(i<=(N+1)/2)
          for j = 1:i
              H(((j-1)+1):(j) , ((i-j)+1):((i+1-j))) = x(((i-1)+1):(i),:);
          end
      else
          for j = (i+1-(N+1)/2):((N+1)/2)
              H(((j-1)+1):(j) , ((i-j)+1):((i+1-j))) = x(((i-1)+1):(i),:);
          end
      end
  end
  minimize sum_square(Α*x - b)+ reg*norm_nuc(H)
cvx_end

My problem is that this code although ok is quite slow i used it for N=250 and it was ok but for another problem that required N=1200 it was not practical at all. I wonder if there is another solver like ADMM or something else in cvx that could be used as a remedy. Maybe am i missing something? Thanks in advance.

2

Perhaps you can show us the CVX and solver output? To do so, do not use quiet.

How much of the time is before output starts showing, as opposed to after?

Perhaps the CVX model formulation time, which is the time prior to output starting, can be dramatically speeded up by vectorizing the creation of H? But today is your lucky day, because hankel can be used as a keyword in a matrix variable declaration, and thereby accomplishes that for you. So use that, and extract x from it. The Basics — CVX Users' Guide

if the solver is taking a long time, i.e., elapsed time after output starts, then your best bet in CVX might be using Mosek. But for large problems, the large SDP might not necessarily be solved as quickly as you’d like, If you change sum_square to norm, and thereby solve a similar but slightly different problem (requiring a different reg), you might improve the conditioning of the problem, and therefore might make things easier, and faster, for the solver.

3

thanks for your reply as for the output is hard since the code does not run within reasonable time. If im not mistaken the default solver is spd3 so Mosek needs a license no? Im not sure i understand how to declare the Hankel matrix properly with the keyword…

4

You can at least copy and paste what output you have. if you don’t have any output, that means CVX is still working on the model formulation, perhaps getting bogged down with the for loop for hankel matrix creation. Use of hankel keyword instead of for loop should hopefully obviate that.

variable H((N+1)/2,(N+1)/2) hankel

As for solvers, yes, mosek requires a license, which I believe you can get for free if you are an academic or student. SeDuMi and SDPT3 are both free and bundled with CVX, and can handle SDP (needed for norm_nuc), so you can try both of them.

I suggest you read the CVX Users’ Guide in its entirety (it’s not that long).