文档介绍：第 2 章 Lasso问题与LARS算法
在本章中，我们将探讨信号处理的前沿问题 压缩采样。我们从Lasso问
题出发，讨论解决Lasso问题的一般思路，给出两种直观的前向算法并引
出LARS算法，进而介绍由LARS算法解决Lasso问题的改进。接着我们将用这些
算法实现了简单的压缩采样重建技术。
Lasso问题与压缩采样
Lasso (Least Absolute Shrinkage and Selection Operator) 问题最初由学者 Tib-
shirani于1996年提出[6]，用于描述一类有约束的优化问题。下面给出问题的具
体提法。
n n
设xi ∈ R , i = 1, 2, · · · , m是一组自变量， y ∈ R 是因变量。用自变量对因变
量进行线性回归，并限定回归系数β的`1范数不超过某个阈值t。它的数学表达
式为：
⃦ ⃦
⃦ ∑︁m ⃦
(α, β) = arg min ⃦y − βi xi − α⃦ subject to ‖β‖ ≤ t (2-1)
⃦ ⃦ `1
⃦ = ⃦
i 1 `2
写成矩阵形式：
= ‖ − − ‖ ‖ ‖ ≤ t
(α, β) arg min y Xβ α `2 subject to β `1 (2-2)
n×m
其中X = [x1, · · · , xm] ∈ R ，取常数α = y¯ − X¯ β。
可见，Lasso问题是限定了`1范数的线性回归问题。这类问题可以很好地描
述当前流行的压缩采样(Compressive Sampling)技术。事实上，本文的人脸识别
算法也可以看作压缩采样恢复算法的一个变体。因此我们在本节简单地介绍压
缩采样，以及他与Lasso问题的联系。
压缩采样打破了传统采样定理的束缚，使得以远低于奈奎斯特(Nyquist)频
率进行采样并恢复信号成为可能，因此在近些年的信号压缩、模式识别等领域
得到非常广泛的应用[4] [5]。一个采样问题可以用下面方程描述：
yk = ⟨x, φk⟩, k = 1, 2, . . . , n (2-3)
5
m
其中x ∈ R 为待测信号，φk为采样函数（传统时域-频域采样中即为傅里叶级
数）， ⟨·, ·⟩表示内积。
如果采样函数是线性的，(2-3)式可写作
= Φ
yn×1 n×m xm×1 (2-4)
其中Φ ∈ Rn×m为采样矩阵。压缩采样中，我们希望n ≪ m，从而进行大幅度的
数据压缩。采样后 得到结果y ∈ Rn，我们希望能完好地恢复被测信号x ∈ Rm，即
数据还原。
此时(2-4)式为一个不定方程组（方程个数少于未知数个数），一般情况下
方程的解是不确定的，即不可能做到无损还原。信号处理中，我们（符合事
实地）假定x是稀疏的，即x ∈ Rm中只有少数元素非零。这种情况下，Candes、
Tao等证明了，只要采样矩阵Φ满足一定稀疏性条件， x ∈ Rm就可以被无损地恢
复[16] [17]。恢复方法为求解下面一个优化问题：
= Φ