Matrix Recovery🚧
Sparse Vector Recovery
（L₀ Norm Minimization）
新舊向量相減x - y，推廣成一次函數Ax - b。
已知變換矩陣A、向量b，求原始向量x，指定稀疏度k。
argmin ‖Ax - b‖₂² ‖x‖₀ ≤ k
請見後面章節Vector Norm Minimization。
Low-rank Matrix Recovery
（Rank Minimization）
新舊矩陣相減X - M，推廣成一次函數AX - B。
已知變換矩陣A、矩陣B，求原始矩陣X，指定秩大小k。
argmin ‖AX - B‖ꜰ² rank(X) ≤ k
請見後面章節Matrix Norm Minimization。
【尚待確認：AX = B應該要改成A(X) = b？】
Vector Regularization
https://stats.stackexchange.com/questions/17781/ http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/AV0405/UMAR/AVassign2.pdf
sparse regularization: min ‖Ax - b‖₂² + α ‖x‖₀ lasso regularization: min ‖Ax - b‖₂² + α ‖x‖₁ ridge regularization: min ‖Ax - b‖₂² + α ‖x‖₂² 多了二次方，湊公式解
L₀ norm是NP-hard問題，L₁ norm和L₂ norm是P問題。
當A是RIP矩陣，則是P問題。【尚待確認】
L₀ norm和L₁ norm沒有公式解，L₂ norm有公式解。
當A是正規正交矩陣，則有公式解。
Matrix Regularization
rank regularization: min ‖AX - B‖ꜰ² + α rank(X)
nuclear norm regularization: min ‖AX - B‖ꜰ² + α ‖X‖⁎
Frobenius norm regularization: min ‖AX - B‖ꜰ² + α ‖X‖ꜰ²
走火入魔。
Restricted Nullspace Property
null(A) = kernel(A) = {x : Ax = 0}
Ax = b always has unique solution iff null(A) = ∅
大一數學。
Σ(k) = {x : ‖x‖₀ = k}
Ax = b subject to ‖x‖₀ = k
always has unique solution iff null(A) ∩ Σ(2k) = ∅
兩個稀疏度為k的向量，加減之後，稀疏度可能是0到2k。
T(x) = {y : ‖x + y‖₁ ≤ ‖x‖₁}
min ‖x‖₁ subject to Ax = b
always has unique solution iff null(A) ∩ T(x) = ∅
T(x)：加上y之後可以湊出更小的答案。
C(S) = {x : ‖xSᶜ‖₁ ≤ ‖xS‖₁}
min ‖x‖₁ subject to Ax = b and ‖x‖₀ ≤ k
always has unique solution iff null(A) ∩ C(S) = ∅ for all |S| ≤ k
S是k個座標軸。xS只使用那k個座標，稀疏度頂多是k。xSᶜ只使用那k個以外的座標。
C(S)：其餘座標軸可以湊出更小的答案。
由於null(A)可以運用QR分解求得，因此此定理具備實際用處？【尚待確認】
Restricted Isometry Property
Restricted Isometry Property (1-δ) ‖x‖² ≤ ‖Ax‖² ≤ (1+δ) ‖x‖² when ‖x‖₀ = k Johnson–Lindenstrauss Lemma (1-δ) ‖x-y‖² ≤ ‖f(x)-f(y)‖² ≤ (1+δ) ‖x-y‖²
RIP矩陣是多變量平緩函數Lipschitz Function？【尚待確認】
(1-δ) ≤ eigenvalue(A'ᵀA') ≤ (1+δ) A' is any subset of vectors of A
想當然爾，特徵值也在δ倍以內。
RIP是不是定義成奇異值比較好呢？【尚待確認】
‖A'ᵀA' - I‖₂ ≤ δ https://ee227c.github.io/notes/ee227c-lecture22.pdf
移項之後，得到coherent。
不動點遞推法（梯度下降法）收斂性證明。啊就步伐越來越小。
RIP = RSC + RSM。平緩函數硬是看成凸函數。小可仔走味。
spark(A): minimal number of linear dependent columns of A
(L₀ norm minimization when b = 0)
rank(A): maximal number of linear independent columns of A
(gaussian elimation)
http://wwwopt.mathematik.tu-darmstadt.de/spear/slides/Tillmann_Talk_2013_SPARS_Lausanne.pdf
RIP certification is NP-hard. Find smallest δ is NP-hard.
Is any polynomial-time algorithm for spark(A) when A satisfies RIP?【尚待確認】
RIP implies RNSP when δ_2k(A) ≤ 1/3 http://www.cs.cmu.edu/~pradeepr/716/notes/lec11.pdf
這啥玩意？
[Candès 2008] let x* is the solution of min ‖x‖₀ subject to Ax = b when ‖x*‖₀ = k 1. if δ_2k(A) ≤ 1 then x* is the unique solution of min ‖x‖₀ subject to Ax = b 2. if δ_2k(A) ≤ sqrt(2) - 1 then x* is the solution of min ‖x‖₁ subject to Ax = b https://coral.ise.lehigh.edu/katyas/files/OPTML/Lecture17.pdf
當倍率δ足夠小，那麼L₀與L₁的極值相等，而且是唯一解。
然而δ無法迅速求得，導致此定理沒有實際用處。
歷經那漫長地婉轉地靈巧地推導，仍未填滿心中那炙熱的疑惑，只徒留淡淡的哀傷。多少的算式已難追憶，不如歸去，不如歸去。
圖解
minimization：L₁ norm包含了L₀ norm的其中一解？
minimization
min ‖x‖₁ subject to Ax = b
^ __-- Ax = b feasible region
_|-'
_--'/|\
--' //|\\ ‖x‖₁ ≤ k level set
---------+--------->
\\|//
\|/
|
sparsification/approximation：當橢圓位置足夠高、橢圓傾斜角度足夠好，L₁ norm包含了L₀ norm的其中一解？
sparsification
min ‖x‖₁ subject to ‖Ax - b‖₂² ≤ ε
^
| ( ) ‖Ax - b‖₂² ≤ ε feasible region
/|\
//|\\ ‖x‖₁ level set
---------+--------->
\\|//
\|/
|
approximation
min ‖Ax - b‖₂² subject to ‖x‖₁ ≤ k
^
| ((o)) ‖Ax - b‖₂² level set
/|\
/ | \ ‖x‖₁ ≤ k feasible region
---------+--------->
\ | /
\|/
|