Least Square and Least Norm – Duality

by allenlu2007

本文主要參考 Boyd 的 CVX101 lecture and note.

Least square (LS) 算是最早 (from Gauss) 的 optimization 方式之一。

LS optimization 廣泛用於 data fitting (Gauss 就是用 LS 找出行星軌道), statistics (ML estimation), control, machine learning, etc.

LS 也稱為 L2 norm.  最主要的好處是數學上漂亮,有 close form.  但並非只有 LS optimization; 也可以用最小絕對值 (L1 norm), 或是 max value (L∞ norm, Chebyshev approximation).  也都各有特點,但沒有 close form.

 

先說結論:

Least square primal problem 如下 (n > k, underfit)

NewImage

where A is tall matrix.  dim(A) = n x k;  dim(x) = k x 1;  dim(b) = n x 1

 

Dual problem 就是 least norm (overfit)

minimize  || u ||2^2   subject to A’ u = A’ b

where A’ is a fat matrix.  dim(A’) = k x n;  dim(u) = n x 1;  dim(A’b) = k x 1

 

假設 n = 2,  k = 1.  

A = [a0, a1]’   b = [b0, b1]’

ao x = b0

a1 x = b1

two points in 2-D space.  Find the slope of line (pass origin) with minimum least square error

 

For LN

a0 u0 + a1 u1 = a0 b0 + a1 b1.  Given a line find the minimum distance to origin

 

如果 k > n  (n=k with only 1 solution)

Ax – b = 0 is the minimum for || Ax – b ||.  所以需要 regularization || x ||^2.

因此自動變成 LN problem, 但並非完全一致。因為 Ax = b 不一定要成立。

 

 

什麼是 Least Square Optimization

可以用一個 data fitting 的例子來說明。假設測量的 data 如下紅點,如何找到最佳的 affine function?

測量包含 n 個 data 如 (a1, b1), (a2, b2), …, (an, bn)

假設 affine function 是:  y = w1 * x + w2   where w1 斜率, w2 是截距

LS error = (w1 * a1 + w2 – b1)^2 + (w1 * a2 + w2 – b2)^2 + … + (w1 * an + w2 – bn)^2

接下來可以對 w1, w2 微分求解。

 

NewImage

 

有沒有更好的解法?  Yes, 可以放在一個 general optimization framework.

NewImage

 dim A = n x k (n: sample; k: unknown parameter/feature)

一般 n >> k,  A 是 tall and narrow matrix!!  代表 parameter space 是 under-fit. 

這是從 machine learning 的角度。如果從解 linear equation 來看,是 over-dtermined.

 dim x = k x 1

 dim b = n x 1

NewImage

如前所述 LS optimization 是有 close form 如下。

NewImage

Computation time proportional to k^2 * n.

最佳解 p* 如下:

NewImage

 

 

LS: minimize  || Ax – b ||2^2 的幾何詮釋

dim A = n x k ;    dim x = k x 1 ;   n >> k

表示 x 從 low dimension (k) map (A) 到 high dimension (n); 同時要儘量像 b (minimize L2 error).

可以分為兩步:  (1)  R(A) 和 b 最接近的 vector;  (2) 找到對應 optimized x* such that  A x* in R(A). 

 

LS 的 estimation 詮釋

就是以上的例子。  

y = A x + v  

where y are measurements (nx1), x are unknown parameters (kx1), v is measurement error (nx1).

假設 v=0,  y = A x,   如果 A 是 tall matrix, 可以看出解 linear equation 是 over-determined.  所以要加入 noise, 而找最佳的 x*.

x* 是 LS optimized solution; 對應的就是 Gaussian noise 的 ML estimation (見前文). 

 

LS 的 optimal design 詮釋

TBD.  A 可以是 input data, b 是 output data.   x 是 channel model. ?

 

 

什麼是 Least Norm Optimization (參考 Boyd EE263 note)

Least norm optimization 問題如下。

NewImage

 

 dim A = m x n (m: data; n: unknown parameter/feature)

 dim x = n x 1

 dim b = m x 1

一般 n > m,  A 是 wide and short matrix!!  代表 parameter space 是 over-fit.  但是從解 linear equation Ax=0 來看,是 underdetermined. 

 

Least norm optimization 常見於有多種方法達到目的 (Ax=b), 最佳解是用最少 resource ( ||x|| ) 的方法。常見於 fuel minimization, etc.  

 

Least Norm 的代數幾何詮釋

假設 xp 是 Ax = b 的一個 solution.   xp + z 也是 solution,  where z ∈ N(A), null space of fat A.

最佳的解就是 minimize  || xp + z ||. 

 NewImage

一個可能解是 (y=b) 如下,可以代入 A xln = b 的確是一個 xp.

NewImage

事實上,xln 不但是 Ax = b 的可能解,也是最佳解!!

此時最佳 solution

p* = || xln ||2^2 = b’ (AA’)^(-1)A A’ (AA’)^(-1) b = b’ (AA’)^(-1) b

dim(AA’) = m x m   dim(b’) = 1 x m –>  p* = b’ (AA’)^(-1) b

如何証明如下:

NewImage

幾何詮釋如下圖:

NewImage

NewImage

NewImage

 

比較一下,LS 的 A matrix 是 tall and narrow (skinny matrix A).  

最佳 solution 

NewImage

兩者有關係嗎?  Yes. 數學上看來很像如下。

NewImage

 

 

除了數學上 LS 和 LN 很相像之外,是否有其他相關性?  Yes.

* Both LS and LN 都是 optimization 問題

* Both LS and LN 都是 convex optimization

* LS and LN 是 (Lagrange) duality 問題

* 最重要的是 duality gap = 0; primal and dual 的最佳值一樣。

 

下面會提到 LS 和 LN 其實是 Lagrange duality optimization problems.

 

LS primal =>  LN dual

先從 LS primal optimization, 導出 dual optimization problem.

 NewImage

一個問題是 LS 看似沒有任何 constraints, 這和 Lagrange dual 的做法乍看有衝突。

不過可以引入 extra variable y = Ax – b, 而造出 linear contraints.  可以參考 Boyd CVX101 lecture 如下。

NewImage

注意要把上述的 b -> -b,  and fo(y) = ||y|| 2^2.  這時原來 unconstrained LS 就可以轉出 dual problem 如上。重新改寫 dual problem 如下:

NewImage

代入 fo*(v) 

NewImage

已經可以看出 LN 的雛型。再做一個 change of variable.

NewImage

Wala!  LS optimization 的 Lagrange dual problem 是 LN optimization.

下一步是確認兩者的 optimal value 相等 (p* = d*).  我們利用上面 LS and LN 的 optimal value

証明兩者相等如下。

NewImage

再確認 x* (primal) 和 u* (dual) 的關係。由上文

x* = (A’ A)^(-1) A’ b

u* = Aln’ (Aln Aln’)^(-1) bln = A (A’ A)^(-1) A’b = A x*  !!!!

所以不但 optimal value 相等 (as expected),  primal x* 和 dual u* 也有簡單關係。

 

這種簡單關係在其他 convex optimization 不一定存在。如果存在,提供一個很有用的方法

用 dual 去算 primal!  例如在 SVM, primal 的 w 很難算,但 dual 的 a 好算 (SMO), 可以從 

a 算出 w.  事實上,不用算 w, 而算最後的 testing function, 而得到 kernel 結果!

 

另外  LS 的

dim(A) = n x k  (skinny matrix)

dim(x) = k x 1

dim(b) = n x 1

 

對應的 LN

A(LN) => dim(A’) = k x n (fat matrix)

dim(u) = n x 1

b(LN) => dim(A’b) = k x 1

 

LN primal =>  LS dual

現在反過來用 LN 做為 primal, 導出 LS 為 dual.

NewImage

此時 A 是 fat matrix (k x n),  dim(x) = n x 1,  dim(b) = k x 1

 

Review 一下,  LN primal 的 optimal solution 如下:

x* = 

NewImage

p* = b’ (AA’)^(-1) b

 

再來看 dual problem:  dim(v) = k x 1

NewImage

NewImage

所以 dual problem 可以改為

minimize 1/4 v’ A A’ v + b’v  = || A’/2 v + A'(AA’)^(-1)b ||2^2  –  b’ (AA’)^(-1) b

因為  b’ (AA’)^(-1) b 只是常數。因此 LN 的 dual problem 是 LS.

同樣確認 dual 的 optimal value  

 

A(LS) = A’/2

b(LS) = -A'(AA’)^(-1)b

從上文 LS 的 optimal value 如下

NewImage

where 

NewImage

x* = 4 (AA’)^(-1) A/2 * (-1)A'(AA’)^(-1) b =  -2* (AA’)^(-1) b

恰好 Als x* – bls = – A’ (AA’)^(-1) b + A’ (AA’)^(-1) b = 0, 也就是 || Ax* – b || = 0

 

也可重算:  

– p* =  – [b’ (AA’)^(-1)A] [A'(AA’)^(-1)A] [A'(AA’)^(-1)b] +  [b’ (AA’)^(-1)A] [A'(AA’)^(-1)b] – b’ (AA’)(-1) b

= – [b’ (AA’)^(-1) b] +  [b’ (AA’)^(-1) b] – b’ (AA’)(-1) b

= – b’ (AA’)^(-1) b

 

p* = b’ (AA’)^(-1) b 和 LN 的結果相同。 QED 

 

How about LS with Regularization!!!!!!!

Great ideal because

1.

2.

3. 

 

 

Advertisements