http://freemind.pluskid.org/machine-learning/sparsity-and-some-basics-of-l1-regularization/

Sparsity 是当今机器学习领域中的一个重要话题。John Lafferty 和 Larry Wasserman 在 2006 年的一篇评论中提到：

Some current challenges … are high dimensional data,sparsity,semi-supervised learning,the relation between computation and risk,and structured prediction.John Lafferty and Larry Wasserman. Challenges in statistical machine learning. Statistica Sinica. Volume 16,Number 2,pp.307-323,2006.

Sparsity 的最重要的客户大概要属 high dimensional data 了吧。现在的机器学习问题中，具有非常高维度的数据随处可见。例如，在文档或图片分类中常用的bag of words模型里，如果词典的大小是一百万，那么每个文档将由一百万维的向量来表示。高维度带来的的一个问题就是计算量：在一百万维的空间中，即使计算向量的内积这样的基本操作也会是非常费力的。不过，如果向量是稀疏的的话（事实上在 bag of words 模型中文档向量通常都是非常稀疏的），例如两个向量分别只有 L1 和 L2 个非零元素，那么计算内积可以只使用 min(L1,L2) 次乘法完成。因此稀疏性对于解决高维度数据的计算量问题是非常有效的。

当然高维度带来的问题不止是在计算量上。例如在许多生物相关的问题中，数据的维度非常高，但是由于收集数据需要昂贵的实验，因此可用的训练数据却相当少，这样的问题通常称为small n ,large p problem——我们一般用 n 表示数据点的个数，用 p 表示变量的个数，即数据维度。当 p≫n 的时候，不做任何其他假设或者限制的话，学习问题基本上是没法进行的。因为如果用上所有变量的话， p 越大，通常会导致模型越复杂，但是反过来 n 有很小，于是就会出现很严重的 overfitting 问题。例如，最简单的线性回归模型：

使用 square loss 来进行学习的话，就变成最小化如下的问题

这里 X=(x1,…,xn)T∈Rn×p 是数据矩阵，而 y=(y1,…,yn)T 是由标签组成的列向量。该问题具有解析解