1.3 LASSO 與匹配追蹤

動機

迴歸模型可以列出許多候選特徵，但一個有用的描述未必需要全部特徵。 最小二乘衡量預測值與觀測值的差距，卻沒有直接表達「只使用少量特徵」的偏好。 LASSO 在係數上加入絕對值懲罰，利用零點的尖角令部分係數恰好變成零。 匹配追蹤則從另一個決定入手：每次選出一個有用方向，更新仍未解釋的殘差。

這些方法都使用殘差與相關量，但所處理的數學目標不同。 殘差小，表示對目前觀測反應的擬合好；LASSO 的解還要平衡擬合程度與係數懲罰。 貪婪序列可以逐步檢查更新，而全局最小值需要同時滿足每一個特徵的最優性條件。 把這幾種條件分清楚，才容易解讀計算結果，也容易找出某一步是否用錯目標。

特徵的尺度本身是模型的一部分。把某欄乘上一個很大的數，便可用相應較小的係數 產生同一項預測貢獻。因此，係數的絕對值懲罰依賴特徵的計量單位。 以訓練觀測值決定居中與縮放方式，才能給懲罰一個明確含義；後來的觀測值沿用 相同轉換，而不是重新定義這個模型的尺度。

定義

定義

LASSO 的目標函數

設 $A=[a_1,\ldots,a_p]\in\mathbb R^{n\times p}$ 是固定特徵矩陣， $y\in\mathbb R^n$ 是反應向量，且 $\lambda>0$。考慮最小化

$$F_\lambda(\beta)=\frac12\|y-A\beta\|_2^2+\lambda\|\beta\|_1, \qquad \|\beta\|_1=\sum_{j=1}^p|\beta_j|.$$

殘差為 $r=y-A\beta$。此定義對每一個係數都施加懲罰。

前面的 $1/2$ 決定下文的閾值。刪去它而保留同一個數值的 $\lambda$，便改變了問題。 同樣地，把平方損失除以觀測數，也會改變固定懲罰的相對強度。 若模型設有不受懲罰的截距，須把它當作另一個參數：它的駐點條件是 $\mathbf1^Tr=0$，不能把截距係數放進軟閾值公式。本節例子沒有額外截距。

目標函數的兩項都是凸函數，因此整體也是凸的。又因為 $F_\lambda(\beta)\ge\lambda\|\beta\|_1$，當係數向量無界增大時，目標值也無界增大， 所以最小值可以取得。若矩陣各欄線性獨立，平方損失嚴格凸，解便唯一。 欄向量相依時，則不能一般地宣稱係數唯一。

定義

字典原子與追蹤狀態

在追蹤計算中，非零欄向量 $a_j$ 稱為原子。每個狀態包括係數 $\beta$ 及滿足 $r=y-A\beta$ 的殘差。普通匹配追蹤從 $\beta=0$、$r=y$ 開始， 每次加上一個原子的倍數；同一個原子可以再次被選中。

定理/命題

命題

以殘差相關量判斷 LASSO 最優性

向量 $\beta$ 最小化 $F_\lambda$，當且僅當每個 $j$ 都滿足

$$\begin{aligned} \beta_j\ne0&\Longrightarrow a_j^Tr=\lambda\operatorname{sign}(\beta_j),\\ \beta_j=0&\Longrightarrow |a_j^Tr|\le\lambda. \end{aligned}$$

所以零係數容許一整段相關量，而不是要求相應相關量必須為零。

命題

正交歸一特徵的軟閾值

若 $A^TA=I_p$，並設 $z=A^Ty$，則唯一的 LASSO 最小值點為

$$\beta_j=S_\lambda(z_j),\qquad S_\lambda(t)=\operatorname{sign}(t)\max(|t|-\lambda,0).$$

這裏 $S_\lambda(0)=0$。相關量的絕對值不超過 $\lambda$ 時，係數為零； 超過閾值時，則把其大小減去 $\lambda$。

命題

普通匹配追蹤一步的精確能量下降

對非零原子 $a_j$ 及目前殘差 $r$，使 $\|r-\alpha a_j\|_2^2$ 最小的倍數為 $\alpha=(a_j^Tr)/\|a_j\|_2^2$。新殘差滿足

$$\|r-\alpha a_j\|_2^2 =\|r\|_2^2-\frac{(a_j^Tr)^2}{\|a_j\|_2^2}, \qquad a_j^T(r-\alpha a_j)=0.$$

要取得最大的一步下降量，應最大化右方的商。 若各原子都是單位向量，這等價於最大化 $|a_j^Tr|$。

第一個條件也能找出整個係數向量變成零的範圍。在 $\beta=0$ 時，殘差是 $y$， 所以所有零座標條件成立，當且僅當 $\lambda\ge\max_j|a_j^Ty|$。 這給出考察一系列懲罰參數時的一個起點。把參數降至此水平以下，零向量便會 違反至少一個相關量條件。這個判準描述指定的訓練問題；若要選擇用於預測的懲罰， 仍須在沒有參與該次擬合的觀測值上評估模型，不能單憑零係數的數目決定。

零點的區間正是此現象的關鍵。平方係數懲罰在零點的導數只有一個值， 絕對值卻可以平衡一整段非零的損失梯度。因此，閾值化是懲罰函數的結構， 而不是先算出稠密解，再把小數值隨意捨去的四捨五入規則。

證明思路

平方損失對 $\beta_j$ 的偏導數是 $-a_j^Tr$。當係數為正，$|\beta_j|$ 的導數為 $1$； 當係數為負，導數為 $-1$。在零點，支持斜率（次梯度）的集合是 $[-1,1]$。 因此，凸最優性條件為 $0\in-A^Tr+\lambda\partial\|\beta\|_1$，即第一個命題。 凸性使它同時是充分與必要條件：若零是目標函數的一個支持斜率， 移到任何其他向量都不能降低目標值。

對正交歸一的欄向量，展開可把座標分離：

$$F_\lambda(\beta) =\frac12(\|y\|_2^2-\|z\|_2^2) +\sum_{j=1}^p\left(\frac12(\beta_j-z_j)^2+\lambda|\beta_j|\right).$$

對單一座標 $t$，正的最小值點須滿足 $t-z+\lambda=0$，而此解位於正半軸， 當且僅當 $z>\lambda$。負的最小值點須滿足 $t-z-\lambda=0$，而此解位於負半軸， 當且僅當 $z<-\lambda$。在餘下區間，零點左導數不大於零，右導數不小於零， 所以零使座標函數最小。這便完整導出三種情況，包括兩個邊界。

最後，把普通追蹤一步展開為 $\|r\|_2^2-2\alpha a_j^Tr+\alpha^2\|a_j\|_2^2$，再完成平方。 因為 $\|a_j\|_2^2>0$，最小化增量唯一。代回便得到能量恆等式， 以及新殘差與所選原子的正交性。這兩個結論都不要求其他原子與它正交。

例題

例題

例題 1：係數在閾值處消失

取 $A=I_2$、$y=(3,-1)^T$ 及 $\lambda=1$。相關量就是反應向量的分量， 所以軟閾值給出

$$\beta=(2,0)^T,\qquad r=(1,-1)^T,\qquad F_1(\beta)=3.$$

平方損失為 $(1^2+(-1)^2)/2=1$，懲罰為 $2$。 第一個殘差相關量等於 $1$，符合正係數的條件；第二個等於 $-1$， 仍在零係數容許的區間內。等於區間端點，並不迫使該係數變成負數。

零向量的目標值為 $5$，無懲罰的完全擬合 $\beta=y$ 的目標值則為 $4$。 最小值點平衡了擬合與係數大小，故兩者都不是這個問題的解。 若改取 $\lambda=1/2$，解為 $(5/2,-1/2)^T$，其目標值為 $1/4+3/2=7/4$。此時目標函數本身也不同，不能把兩個最小值當作同一把尺度 來選擇 $\lambda$。

例題

例題 2：同一原子再次發揮作用

設 $a_1=(1,0)^T$、$a_2=(1,1)^T/\sqrt2$，且 $y=(0,1)^T$。 兩個原子都長度為一。起初相關量為 $0$ 及 $1/\sqrt2$，所以先選 $a_2$。 普通匹配追蹤前三步得到下表；各欄依次是步數、所選原子，以及係數與殘差的轉置（按行展示）：

$$\begin{array}{c|c|c|c} k&j&\beta^T&r^T\\ 0&-& (0,0)&(0,1)\\ 1&2&(0,1/\sqrt2)&(-1/2,1/2)\\ 2&1&(-1/2,1/\sqrt2)&(0,1/2)\\ 3&2&(-1/2,3/(2\sqrt2))&(-1/4,1/4) \end{array}$$

殘差平方範數依次是 $1$、$1/2$、$1/4$、$1/8$。 第二步在 $a_1$ 上加上增量 $-1/2$，移除了第一個殘差座標， 卻令殘差再次與 $a_2$ 有相關。第三步在 $a_2$ 上的增量為 $1/(2\sqrt2)$， 必須加到已有係數上；若覆寫原係數，便會破壞 $r=y-A\beta$。

例題

例題 3：重擬合所選張成空間

選中上述兩個原子後，正交匹配追蹤以最小二乘同時重擬合兩個係數。 由 $\beta_1+\beta_2/\sqrt2=0$ 及 $\beta_2/\sqrt2=1$ 得

$$\beta_{\mathrm{OMP}}=(-1,\sqrt2)^T,\qquad r_{\mathrm{OMP}}=0.$$

普通匹配追蹤兩步後的係數仍是 $(-1/2,1/\sqrt2)^T$，殘差平方範數為 $1/4$。 重擬合使用的是整個所選張成空間，並非只再減去最新原子的另一種說法。

完全擬合與 LASSO 最優性也不同。取 $\lambda=1/4$ 時，OMP 向量的 $F_{1/4}=(1+\sqrt2)/4$；兩步 MP 向量的 $F_{1/4}=1/4+\sqrt2/8$，反而較小，雖然其殘差非零。 這個比較尚未證明 MP 向量是 LASSO 的解，卻說明只檢查殘差的停止判準 不能認證帶懲罰目標的最優性。

座標更新與貪婪更新

一般特徵矩陣不能把正交歸一情況的公式同時套在所有座標上， 但對非零欄 $a_j$，仍可精確解出單一座標子問題。 固定其他係數，設 $r_{-j}=r+a_j\beta_j$，即把目前第 $j$ 項的貢獻加回， 留下容許此座標解釋的反應。最小化 $\|r_{-j}-a_jt\|_2^2/2+\lambda|t|$ 得

$$\beta_j^{\mathrm{new}} =\frac{S_\lambda(a_j^Tr_{-j})}{\|a_j\|_2^2}, \qquad r^{\mathrm{new}}=r-a_j(\beta_j^{\mathrm{new}}-\beta_j).$$

這裏更新的是整個係數。若原子已經使用過，僅以 $\lambda|\alpha|$ 懲罰新增量， 便是另一個單步目標；全局懲罰涉及的是 $|\beta_j+\alpha|$。 計算完係數後，可以用所有殘差相關量檢查 LASSO 條件，而不依賴所用演算法的名稱。

令 $c=\|a_j\|_2^2>0$、$\rho=a_j^Tr_{-j}$，便可看清分母的來源。 除去與 $t$ 無關的項，座標目標為 $ct^2/2-\rho t+\lambda|t|$。 正、負兩邊的駐點方程分別是 $ct=\rho-\lambda$ 與 $ct=\rho+\lambda$， 中間由零填補。因此，即使整個矩陣的欄相依，這個非零欄的座標子問題仍嚴格凸。 對零欄，直接最小化其懲罰便令相應係數為零。

若追蹤殘差與每一個原子的相關量都為零，它便垂直於整個可用特徵空間， 因而滿足普通最小二乘的正規方程。此時殘差長度仍可以為正， 因為未解釋部分位於該空間之外。在此之前，能量恆等式衡量下一步可取得的改善。 例題 2 的能量持續減半，說明逼近精確表示未必會在有限步普通 MP 內達成。 指定步數是從這個序列中選擇模型，與選擇 LASSO 的係數懲罰是不同決定。

以下程式追蹤例題 2 的普通 MP。它按能量下降量選取原子，所以同一式子也適用於 非單位原子。

import numpy as np

A = np.array([[1.0, 1.0 / np.sqrt(2.0)],
              [0.0, 1.0 / np.sqrt(2.0)]])
y = np.array([0.0, 1.0])
beta = np.zeros(2)
residual = y.copy()
norm2 = np.sum(A * A, axis=0)
for step in range(3):
    correlation = A.T @ residual
    j = int(np.argmax(correlation ** 2 / norm2))
    increment = correlation[j] / norm2[j]
    beta[j] += increment
    residual -= increment * A[:, j]
    energy = float(residual @ residual)
    print(f"{step + 1}: atom={j + 1}, beta=({beta[0]:.6f}, {beta[1]:.6f}), energy={energy:.6f}")
omp, _, _, _ = np.linalg.lstsq(A, y, rcond=None)
assert np.allclose(omp, [-1.0, np.sqrt(2.0)])

1: atom=2, beta=(0.000000, 0.707107), energy=0.500000
2: atom=1, beta=(-0.500000, 0.707107), energy=0.250000
3: atom=2, beta=(-0.500000, 1.060660), energy=0.125000

帶懲罰的追蹤增量

現在懲罰每步新增的量，並改用未乘 $1/2$ 的平方損失：

$$\widetilde F_\lambda(\beta)=\|y-A\beta\|_2^2+\lambda\|\beta\|_1 =2F_{\lambda/2}(\beta),\qquad\lambda>0.$$

閾值因此是 $\lambda/2$。從 $\beta=0$、$r=y$ 開始，對非零原子記 $\kappa_j=\|a_j\|_2^2>0$、$u_j=a_j^Tr$，求解

$$q_j(\gamma)=\|r-a_j\gamma\|_2^2+\lambda|\gamma| =\|r\|_2^2-2u_j\gamma+\kappa_j\gamma^2+\lambda|\gamma|.$$

這裏直接使用目前殘差，沒有加回原子先前的貢獻；懲罰的是增量，而非更新後的完整係數。

命題

帶懲罰增量及其精確局部改善

唯一最優增量為

$$\gamma_j^*=\frac{S_{\lambda/2}(u_j)}{\kappa_j} =\begin{cases} (u_j-\lambda/2)/\kappa_j,&u_j>\lambda/2,\\ 0,&|u_j|\le\lambda/2,\\ (u_j+\lambda/2)/\kappa_j,&u_j<-\lambda/2. \end{cases}$$

相應局部目標改善量為

$$\Delta_j=q_j(0)-q_j(\gamma_j^*) =\frac{\bigl(\max(|u_j|-\lambda/2,0)\bigr)^2}{\kappa_j}.$$

正半軸的駐點方程為 $2\kappa_j\gamma-2u_j+\lambda=0$，僅在 $u_j>\lambda/2$ 時給出正解；負半軸同理。在零，支持斜率區間包含零的條件 是 $|u_j|\le\lambda/2$。代回二次式便得改善量，故不能只比較兩個非零駐點式。

例如 $a_j=1$、$r=1/2$、$\lambda=2$ 時，最優增量為零，$q_j(0)=1/4$。 候選式給出的 $3/2$、$-1/2$ 均不符合各自分支，目標值為 $4$、$2$，不能取代零。

選最大 $\Delta_j$ 可使局部增量目標下降最多。單位原子或共同正 $\kappa_j$ 下， 選最大 $|u_j|$ 也最大化 $\Delta_j$；長度不同須保留分母。全部分數為零時，各增量均為零。 選定原子後須累加係數，保持殘差恆等式：

$$\beta_j\leftarrow\beta_j+\gamma_j^*,\qquad r^{\mathrm{new}}=r-a_j\gamma_j^*,\qquad \gamma_j^*\ne0\Longrightarrow a_j^Tr^{\mathrm{new}}=\frac{\lambda}{2}\operatorname{sign}(\gamma_j^*).$$

重選原子不能覆寫舊係數。非零懲罰增量留下大小為閾值的相關量，不同於普通 MP 的正交性。

例如 $r=(2,2)^T$、$a=(10,0)^T$、$b=(1,1)^T$、$\lambda=2$， 原始相關量為 $20$、$4$，改善量卻為 $361/100$、$9/2$，原始相關量較大反而改善較小。 分數比較的是指定尺度的原子；若歸一化各欄，也須按新單位解讀係數懲罰。

全局懲罰改變是 $\lambda(|\beta_j+\gamma|-|\beta_j|)$，局部 $q_j$ 卻收取 $\lambda|\gamma|$。以 $e_j$ 表示第 $j$ 個座標單位向量，三角不等式給出

$$\widetilde F_\lambda(\beta+\gamma_j^*e_j) -\widetilde F_\lambda(\beta) \le q_j(\gamma_j^*)-q_j(0)=-\Delta_j.$$

所以正確增量不增加全局目標。未用過的係數使兩項改變相等，重用後則未必； $\Delta_j$ 一般不是精確全局改善。若增量縮小舊係數而未越過零，全局懲罰下降， 增量懲罰卻為正。故 $\Delta_j$ 是全局下降量的下界；最大化它只優化局部分數， 未必最大化實際全局下降量。完整座標最小化會加回舊貢獻，再替換整個係數：

$$\beta_j^{\mathrm{new}} =\frac{S_{\lambda/2}(u_j+\kappa_j\beta_j)}{\kappa_j}.$$

例題

例題 4：增量追蹤可在 LASSO 最優之前停住

取單位欄矩陣

$$A=\begin{pmatrix}1&3/5\\0&4/5\end{pmatrix},\qquad y=(3,1)^T,\qquad\lambda=2.$$

初始相關量為 $(3,13/5)^T$，先選原子 1；下一組為 $(1,7/5)^T$，再選原子 2。 下表分列增量、累計係數與殘差：

$$\begin{array}{c|c|c|c|c} k&j&\gamma&\beta^T&r^T\\ 0&-&-&(0,0)&(3,1)\\ 1&1&2&(2,0)&(1,1)\\ 2&2&2/5&(2,2/5)&(19/25,17/25)\\ 3&2&0&(2,2/5)&(19/25,17/25) \end{array}$$

第二步後相關量為 $(19/25,1)^T$，兩分數皆零；最大相關量規則重選原子 2，增量為零。 但 $\widetilde F_2$ 的正係數條件要求第一個相關量為 $1$，並非 $19/25$。 完整座標更新會令 $\beta_1=44/25$，使目標下降 $36/625$。

全局解其實為 $(13/8,5/8)^T$，殘差 $(1,1/2)^T$ 的兩個相關量均為 $1$， 符合正係數條件；目標值 $23/4$ 小於停住時的 $146/25$。 兩值分別是 $5/4+9/2$ 與 $26/25+24/5$，即殘差平方範數加係數懲罰。 本例兩欄線性無關，故經驗證的全局解在這個矩陣下唯一。 因此，增量目標沒有改善，不等於完整座標已最優，也不保證全局係數條件成立。

約束與平滑懲罰

設 $\beta_\lambda$ 是 LASSO 最小值點，並取 $\tau=\|\beta_\lambda\|_1$。 它也在約束 $\|\beta\|_1\le\tau$ 下最小化平方損失。 否則，可找到可行向量，其損失更小、懲罰不更大，這便違反帶懲罰問題的最優性。 這是從一個指定的懲罰解建構對應約束問題，並不建立 $\lambda$ 與 $\tau$ 的一一對應； 多個懲罰值可能都給出同一個零解。

另一個選擇是以圓滑函數代替絕對值。一種經縮放的 Huber 懲罰為

$$h_\delta(t)=\begin{cases} t^2/(2\delta),&|t|\le\delta,\\ |t|-\delta/2,&|t|>\delta, \end{cases}\qquad\delta>0.$$

它在外側的斜率為一，且 $\delta\to0$ 時 $h_\delta(t)\to|t|$。另一個選擇是 歸一化的 pseudo-Huber 懲罰：

$$p_\delta(t)=\sqrt{t^2+\delta^2}-\delta,\qquad\delta>0.$$

歸一化後的導數清楚表達了兩者的光滑性：

$$h_\delta'(t)=\begin{cases} t/\delta,&|t|\le\delta,\\ \operatorname{sign}(t),&|t|>\delta, \end{cases} \qquad p_\delta'(t)=\frac{t}{\sqrt{t^2+\delta^2}},\qquad p_\delta''(t)=\frac{\delta^2}{(t^2+\delta^2)^{3/2}}>0.$$

在 $t=\pm\delta$，Huber 的一階導數接合，但二階導數由 $1/\delta$ 變成零， 因此它在此處連續可微，卻非二次可微。Pseudo-Huber 則處處光滑。兩者在零的 曲率皆為 $1/\delta$，外側極限斜率的大小皆為一。若改用 $\delta h_\delta$ 或 $\delta p_\delta$，固定 $\lambda$ 下的懲罰貢獻會乘以 $\delta$，故須同時交代 尺度與平滑寬度。

對 $\lambda>0$，考慮 $G(t)=(t-z)^2/2+\lambda h_\delta(t)$。在二次區域， $G'(t)=t-z+\lambda t/\delta=0$ 給出 $t=\delta z/(\delta+\lambda)$；它屬於 該區域，當且僅當 $|z|\le\delta+\lambda$。外側的駐點方程為 $t-z+\lambda\operatorname{sign}(t)=0$。選取符合區域條件的分支，得到

$$t_*=\begin{cases} \delta z/(\delta+\lambda),&|z|\le\delta+\lambda,\\ z-\lambda\operatorname{sign}(z),&|z|>\delta+\lambda. \end{cases}$$

在 $z=\pm(\delta+\lambda)$，兩式都給出 $t_*=\pm\delta$。平方損失嚴格凸， 懲罰為凸，因此這個駐點是唯一全域最小值點。使用任一平滑懲罰時，單變量目標 在零的導數均為 $-z$；最小值點為零，當且僅當 $z=0$，與 LASSO 的零值區間 不同。這裡平滑的是係數懲罰；把殘差損失換成 Huber，是另一個迴歸目標。

常見錯誤

常見錯誤

混淆相關量、重擬合與最優性

對非單位原子，最大原始相關量未必帶來最大的殘差能量下降， 須把相關量平方除以原子平方範數。 普通 MP 的殘差垂直於最近選中的原子；OMP 的最小二乘殘差則垂直於每一個已選欄。 這些觀察本身都沒有檢查所有欄的 LASSO 懲罰條件。

係數的稀疏性亦依賴表示方式。高度相關的特徵可能互相分擔貢獻，卻保留相近預測。 被選中的特徵屬於一個有指定單位與懲罰的模型，並不直接構成因果關係的結論。

例如取 $A=[1,1]$、反應 $y=3$ 及 $\lambda=1$。 寫成 $t=\beta_1+\beta_2$，三角不等式給出 $|\beta_1|+|\beta_2|\ge|t|$。單一座標問題的最優 $t=2$，而每個 $(2-s,s)^T$、$0\le s\le2$ 都取得相同目標值 $3$。 部分向量只有一個非零係數，其他則有兩個；預測反應始終相同，特徵表示卻不唯一。 因此，不能僅由採用絕對值懲罰便推斷係數唯一。

總結

絕對值懲罰的尖角容許係數恰好為零。對正交歸一特徵和單座標子問題， 軟閾值把這個機制寫成明確公式。普通匹配追蹤每次控制一個原子的殘差能量變化； 重新擬合整個已選張成空間得到 OMP。若要判斷 LASSO 最優性， 則須把所有殘差相關量與相應懲罰條件逐一比較。

練習

思考檢查

練習 1：設 $A=I_3$、$y=(2,-1/2,0)^T$、$\lambda=1$。求 LASSO 係數、殘差及目標值。

對每一個反應分量使用軟閾值，包括中間分量。

思考檢查

練習 2：對殘差 $r=(1,1)^T$，比較原子 $a=(10,0)^T$ 及 $b=(1,1)^T$。哪個原始相關量較大？哪個移除更多殘差平方能量？

計算相關量平方除以原子平方範數。

思考檢查

練習 3：在例題 2 中，求第四步 MP 的增量、係數及殘差平方範數。

從殘差 $(-1/4,1/4)^T$ 開始，先比較兩個相關量。

思考檢查

練習 4：單一座標 LASSO 問題有 $A=[1]$、$y=1/2$、$\lambda=1$。檢查候選係數 $0$。只考慮非零駐點會漏掉甚麼？

絕對值在零點的支持斜率形成一個區間。

思考檢查

練習五：對 $(t-z)^2/2+\lambda h_\delta(t)$，取 $\delta=1/2$、$\lambda=1$。分別求 $z=1/4$、$z=3/2$ 的最小值點，並把第一個結果與單變量 LASSO 比較。

兩個解分支之間的邊界是 $\delta+\lambda$。

解答

解答 · 練習 1 解答

係數為 $(1,0,0)^T$，殘差為 $(1,-1/2,0)^T$。 目標值為 $(1+1/4)/2+1=13/8$。兩個零座標的殘差相關量都位於 $[-1,1]$。

解答 · 練習 2 解答

原始相關量為 $10$ 和 $2$，但能量下降量為 $10^2/100=1$ 和 $2^2/2=2$。 原子 $b$ 移除了整個殘差，原子 $a$ 只移除第一座標。 把選擇分數正規化，可避免僅由原子長度造成的偏好。

解答 · 練習 3 解答

與 $a_1$ 的相關量為 $-1/4$，與 $a_2$ 的相關量為零， 所以在 $a_1$ 上加上第四個增量 $-1/4$。 係數變成 $(-3/4,3/(2\sqrt2))^T$，殘差變成 $(0,1/4)^T$，平方範數為 $1/16$。

解答 · 練習 4 解答

在零點，$r=1/2$，相關量 $1/2$ 位於 $[-1,1]$，所以滿足凸最優性條件。 正半軸的方程給出 $t=-1/2$，不在正半軸；負半軸的方程給出 $t=3/2$， 也不在負半軸。這些無效候選點不能取代零點情況。 真正的零點目標值為 $1/8$。

解答 · 練習五解答

分支邊界為 $3/2$。當 $z=1/4$，二次區域公式給出 $t_*=(1/2)(1/4)/(3/2)=1/12$，確實在 $|t|\le1/2$ 內；單變量 LASSO 卻給出 $S_1(1/4)=0$。當 $z=3/2$，兩式都給出 $t_*=1/2$：內側為 $(1/2)(3/2)/(3/2)$，外側為 $3/2-1$。這同時檢查了邊界與平滑造成的非零效果。

相關筆記

最小二乘與殘差 建立本節使用的殘差幾何。 模型驗證與嶺迴歸 討論懲罰參數的選擇及二次懲罰對擬合的影響。 奇異值分解與主成分 研究數據中的正交方向。課程書目 集中列出可進一步閱讀的書籍。