Least Squares with $ {L}_{2} $ (L2) Linear Norm Regularization (Not Squared)

Question

Define $$L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \left\|\frac{w}{x}\right\|,~w,u\in \Bbb{R}^n$$ where $$\frac{w}{x}=\left(\frac{w_1}{x_1},\ldots, \frac{w_n}{x_n}\right)$$ $$\|x\|=\sqrt{x_1^2+\cdots+x_n^2}$$ Given $u$, $x$ and $\beta$, how to get $$\arg\min_{w\in \Bbb{R}^n}L(w,u)$$

Answer 1

$$ L(w,u)=\frac{1}{2}\|w-u\|^2+\beta \|\frac{w}{x}\| =\frac{1}{2}\sum_{i=1}^n (w_i-u_i)^2+\beta\sqrt{ \sum_{i=1}^n \frac{w_i^2}{x_i^2}} $$ Hint :

$$ \frac{\partial L}{\partial w_k}=w_k-u_k+\beta\frac{w_k/x_k^2}{\sqrt{ \sum_{i=1}^n \frac{w_i^2}{x_i^2}}}=0, \qquad k=1,2,\cdots,n $$

Answer 2

Another approach would be defining $ X = \operatorname{diag} \left( \frac{1}{ {x}_{1} }, \frac{1}{ {x}_{2} }, \ldots , \frac{1}{ {x}_{n} } \right) $.

Then the problem becomes:

$$ \arg \min_{w} \frac{1}{2} \left\| w - u \right\|_{2}^{2} + \beta \left\| X w \right\|_{2} $$

Now, remember that $ \nabla_{x} \left\| x \right\|_{2} = \frac{x}{ \left\| x \right\|_{2} } $ then the derivative is given by:

$$ w - u + \beta {X}^{T} \frac{X w}{ \left\| X w \right\|_{2} } $$

with some tweaking:

$$ w = \left( \frac{\beta}{\left\| X w \right\|_{2}} {X}^{T} X + I \right)^{-1} u $$

Now you can use the Iteratively Reweighted Least Squares (IRLS) Approach to calculate $ w $ and since the problem is Convex you'll get your solution.

Pay attention that $ \frac{\beta}{\left\| X w \right\|_{2}} {X}^{T} X + I $ is diagonal hence the inversion is easy.

MATLAB Code:

hObjFun = @(vW) (0.5 * sum((vW - vU) .^ 2)) + (paramBeta * norm(vW ./ vX));

vObjVal = zeros([numIterations, 1]);

vW = vU;
vObjVal(1) = hObjFun(vW);

for ii = 2:numIterations

    % Calculation of the inverse term. Since all diagonlas terms can be
    % done using vectors.
    fctrTerm    = paramBeta / norm(vW ./ vX);
    vXX         = (1 ./ (vX .^ 2));
    vInvXX      = 1 ./ ((fctrTerm * vXX) + ones([numRows, 1]));

    vW = vInvXX .* vU;

    vObjVal(ii) = hObjFun(vW);
end

disp([' ']);
disp(['Iterative Reweighted Least Squares (IRLS) Solution Summary']);
disp(['The Optimal Value Is Given By - ', num2str(vObjVal(numIterations))]);
disp(['The Optimal Argument Is Given By - [ ', num2str(vW.'), ' ]']);
disp([' ']);

The code take advantage of all matrices being diagonal and hence the operations can be element wise which makes the code very simple and efficient.

As can be seen above, the convergence is very quick and the code is efficient.

The full MATLAB code is in my StackExchange Mathematics Q454519 GitHub Repository.