0

I am given a vector x. My objective is to find an optimal y (minimize $||y-x||_2^2$). With the constraint $y(c) = a$ (a and c are known scalars).

$$\text{minimize}_y ||y-x||_2^2 \\ \text{subject to}\ \ y(c) = a $$

Further, I am confused about how to enforce a smoothness constraint. I am aware that in theory we add a regularization term to the objective function $ ||y-x|| + \lambda \bigtriangledown y $

I am trying to use CVX to achieve this. More info on CVX is Matlab Software for Convex Optimization (http://cvxr.com/cvx/) How is it possible to have such a regularization?

mkuse
  • 195

1 Answers1

1

The optimization variable is $y \in \mathbb R^N$. Without a regularization term, the solution to the optimization problem written is the vector that agrees with $x$ except in the $c$th component, which is equal to $a$. You can add a regularization term involving a (discrete) gradient of $y$ as you have mentioned. One popular choice for a regularization term is \begin{equation*} r(y) = \sum_{i=1}^{N-1} |y_{i+1} - y_i|. \end{equation*} With this regularization term, you are solving a "total variation denoising" problem.

The optimization problem including this regularization term is \begin{align} \text{minimize} & \quad \|y - x\|_2^2 + \lambda \sum_{i=1}^{N-1} |y_{i+1} - y_i| \\ \text{subject to}& \quad y_c = a, \end{align} with variable $y \in \mathbb R^N$.

littleO
  • 51,938
  • In order to achieve discrete difference, I need to use matrix multiplication (L*y)? L = [ 1 -1 0 ... 0 ; 0 1 -1 0 .. 0 ; ....]. My problem dimension is very large and I want to avoid this matrix multiplication. I know this can be achieved much more efficiently by use of a sparse matrix.

    Where can I get information on more other techniques to achieve similar regularization?

     – mkuse Oct 21 '14 at 08:09
  • 1
    I think CVX will allow you to express the regularization term in a way that doesn't involve matrix multiplication. Something like sum(abs(y(2:end) - y(1:end-1))). You could try reading section 6.3.3 of Boyd and Vandenberghe (free online). – littleO Oct 21 '14 at 08:15
  • 1
    That's right. I'd write that objective as sum_square(y-x)+lambda*sum(abs(y(2:end)-y(1:end-1))). – Michael Grant Oct 21 '14 at 16:22