How to Formulate in CVX - 1D Total Variation Extension

Uncategorized
Jun 27, 2016
R
#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.

R
#2

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

M
#3

How did you prove the objective function is convex?

R
#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.

1 reply
M
#5
Replying to #4

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

R
#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.

1 reply
M
#7
Replying to #6 
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
1 1 reply
R
#8
Replying to #7

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.

2 replies
M
#9

Nice pedagogical technique there, Mark!

M
#10
Replying to #8

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

1 reply
R
#11
Replying to #10

Well,

This question is solved.

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

M
#12
Replying to #8

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.

R
#13

Has the MathJaX Plug In of the site stopped working?

1 reply
M
#14
Replying to #13

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

1 reply
M
#15
Replying to #14

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

1 reply
R
#16
Replying to #15

Any update on that?

It is crucial to the forum.

Thank You.

M
#17

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

R
#18

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

Maybe they could assist?