一、稀疏解的逼近问题
对于高维稀疏解的逼近问题，可以归结为模型
y=Ax+ϵ
机器学习的回归问题中，为了防止过拟合和提高模型泛化性能，对原始损失函数引入额外惩罚项信息，即
正则化
特别的，当p = 0时，
根据不同的问题，选择合适的参数p 。
正则化可以使得参数稀疏化，从而过滤掉模型的一些无用特征，提高模型的泛化能力，降低过拟合的可能。
正则化可以使得参数平滑，防止模型过拟合。因此对比而言，
正则化更适合处理高维稀疏数据。
下面以二维为例，从优化问题和概率论角度来讨论为什么
正则化产生稀疏模型。
1.1、优化问题角度
此时模型的求解转化为如下的优化问题
将损失函数
投影到
平面，即等值线（如图彩色线条），并分别画出 正则化项和 正则化项（如图黑色线条）
正则化项同拉格朗日乘子的作用一样，起了约束作用。因为当损失函数
的等值线与正则化项首次相交的地方就是最优解。从上图可见，正则化项比 多出4个突出的角，当等值线与这些角相交的机率会大大增加。而在这些角上，某个权值
等于0。当维数增加， 突出的角更多，因此更容易产生稀疏模型。
1.2、概率论问题角度}
正则化相当于为x加入了Laplace先验分布，而 正则化项相当于为x 加入了Gaussian先验分布。
从分布图直观上看，在两端Gaussian分布的概率
小于Laplace分布的概率
，且在中间段Gaussian分布等于0和接近0的分布很接近，说明Gaussian分布下的$\bf x $比较均匀。而Laplace分布等于0处的概率远大于其他部分，说明Laplace分布下的x 存在更多的0元素。
二、 与
正则化的求解
2.2、的软阈值迭代算法
对于连续可微的无约束优化问题
且满足Lipschitz连续条件
根据梯度法，给定初始点
和初始步长t，有
正则化算法
2008年，徐宗本在《 正则化》中证明,正则化子比正则化子具有更好的稀疏性和稳健性。
文献中为了求解 正则化问题，提出重赋权迭代求解思想，将 正则化问题转化为正则化问题
三、算例
3.1、例1——高斯分布矩阵
数据源：
- 随机产生250 × 500的高斯信号矩阵A，矩阵条件数为 5.5415
- 随机产生500 × 1 的高斯分布数据x，再随机令其中20个元素非零，其余为零。。由A x = y ，可3、得到数据y
对得到的数据y ，施加1 % 的随机噪声计算结果：
3.2、例2-积分方程
数据源：
1、考虑一个卷积型积分方程例子：
其中核函数
。当核函数矩阵为20 × 20时，其条件数为2463.
2、随机产生20 × 1 的高斯分布数据x，再随机令其中5个元素非零，其余为零。由K x = y ，可得到数据y
3、对得到的数据y，施加1 %的随机噪声
3.3、例3-Hilbert矩阵
数据源：
1、 产生500 × 500 的Hilbert矩阵A，矩阵条件数为6.8337 × 
2、随机产生500 × 1 的高斯分布数据x，再随机令其中20个元素非零，其余为零。由A x = y ，可得到数据y
3、对得到的数据y，施加1 % 的随机噪声
Hilbert矩阵下的高维稀疏数据反演，不论是正则化还是正则化，得到的结果均不理想，不能将原数据x的稀疏性表现出来，而是将其磨光。但从观测数据y上分析，虽然拟合的y 也被磨光处理，但依旧能较好的拟合真实数据。
经过多次尝试发现，Hilbert矩阵下的高维稀疏数据逼近模型，即A x = y，对于固定的A和y，其解x 不唯一。
这是因为Hilbert矩阵的特征值矩阵高度稀疏，当x也是稀疏数据，运算时将会丢失很多关键信息，因此无法正确反演稀疏数据x 。以16位有限数字为界，则500 × 500的Hilbert矩阵，其特征值矩阵的稀疏密度为93%。
