How to Formulate in CVX - 1D Total Variation Extension


(Royi) #1

Given the problem

\min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} \sqrt{{\left( {x}_{i} - {x}_{i + 1} \right)}^{2} + {\left( {x}_{i + 1} - {x}_{i + 2} \right)}^{2}}

How could one formulate it in CVX?
I could handle it without the sqrt yet couldn’t do it in this form.

Thank You.


(Royi) #2

What if I have a dual form which separable, how could I use it with CVX?


(Mark L. Stone) #3

How did you prove the objective function is convex?


(Royi) #4

Hi @Mark_L_Stone, well, I could rewrite the problem as:

\min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} \sqrt{{\left( {x}_{i} - {x}_{i + 1} \right)}^{2} + {\left( {x}_{i + 1} - {x}_{i + 2} \right)}^{2}} = \min_{ x \in {\mathbb{R}}^{n} } \frac{1}{2} {\left\| x - y \right\|}_{2}^{2} + \sum_{i = 1}^{n - 2} { \left\| {B}_{i} x \right\| }_{2}

Where the matrix {B}_{i} extracts a vector such that

{z}_{i} = {B}_{i} x = \begin{bmatrix} {x}_{i} - {x}_{i + 1} \\ {x}_{i + 1} - {x}_{i + 2} \end{bmatrix}

This must be Convex.

Thank You.


(Mark L. Stone) #5

Well, there you go. Code that up in a straightforward manner, and CVX should accept it.


(Royi) #6

Hi @Mark_L_Stone,

That’s the issue, I don’t know how to insert the Loop into CVX.
It can’t be written in one minimize argument.

Thank You.


(Mark L. Stone) #7
cvx_begin
variable x(n)
Objective = 0.5*sum_square(x-y)
for i=1:n-2
  Objective = Objective + norm([x(i)-x(i+1);x(i+1)-x(i+2)])
end
minimize(Objective)
% insert any other constraints
cvx_end

(Royi) #8

Hi @Mark_L_Stone,

It really solved it.
I wasn’t aware it can be done that way (Looping inside CVX Block).

Is there a way to mark question as solved?

Thank You.


(Michael C. Grant) #9

Nice pedagogical technique there, Mark!


(Mark L. Stone) #10

There is no marking questions as solved in this forum. Your post stating that it is solved will accomplish that purpose for readers.


(Royi) #11

Well,

This question is solved.

CVX is really awesome.
Just need better support for large size arrays.


(Mark L. Stone) #12

Now that you have some experience with CVX, perhaps you should re-read the CVX Users’ Guide, so that you can pick up on things which you didn’t fully absorb the first time.


(Royi) #13

Has the MathJaX Plug In of the site stopped working?


(Mark L. Stone) #14

Is is not displaying for me either, in 2 different browsers.


(Michael C. Grant) #15

Yeah, it seems busted and I as yet do not know how to fix it.


(Royi) #16

Any update on that?

It is crucial to the forum.

Thank You.


(Michael C. Grant) #17

No, I’d love it if someone would figure it out! I have not succeeded.


(Royi) #18

The guys over Julia are using the same forum and have it working.

Maybe they could assist?