教科书的算法是最小化

其中$\|x\|_0$计算非零系数的数量。由于这对于确定下降方向是一个不好的函数，因此将计数范数软化为

对于一些小的$ε$值。例如，对于$|x_k|>\exp(-\tfrac1{\sqrtε})$，这是一个非常小的阈值，一个得到$|x_k|^ε>\exp(-\sqrtε)\ge 1-\sqrtε$，所以所有不太小和不太大的值都被映射到$1$，只有非常小的值被映射到零。

为了得到一个真正平滑的函数，主要是出于理论目的，可以通过使用在$0$

并且显然选择以使仍然映射到接近，例如通过选择。$δ$$x_k=0$$0$$δ=\exp(-\tfrac1{\sqrtε^3})$

既然这个答案与当前形式的问题完全正交，我希望其他人对矩阵选择的主题有更深入的了解。我所知道的是：

起初，在压缩或压缩感知作为词存在之前，是小波或类小波系数的矩阵。基于小波的压缩（和JPEG）的整个想法是将小系数归零（并截断非零系数的二进制表示）。这可以通过在多个尺度上观察和利用细节系数的相关性在一个方向上得到改进，或者在另一个方向上通过使基向量更加不相关并因此减少那些分形特征来改进。$A$

也可能存在从随机矩阵开始并根据某些帧条件修改或拒绝它的算法。

DCT 在实践中经常使用，例如在经典的非小波版本JPEG中。

给定一个基矩阵 A，有许多算法可以找到解向量 x。但是您要问的是如何找到基矩阵 A。

在许多问题中，您可以选择它。例如，在稀疏频率估计问题中，A 的列对应于特定频率下特定复指数的样本。

还有一些算法可以处理离网问题，即当基向量与您的数据略有偏差时。大多数算法从一组假设的向量开始，然后使用梯度下降方法来修改基向量。

另一组算法称为字典学习算法。这些算法倾向于使用训练数据库来找到一组好的基向量。

我发现 Michael Elad 的书 - Sparse and Redundant Representations 非常好。这不是太数学 - 他还有一章关于字典学习算法。Candes 在 IEEE 信号处理杂志中也有一些类似教程的文章。在 Melvin, Scheer 的“现代雷达原理 - 高级技术”中也有一个非常好的关于压缩感知的章节，提供了很好的概述和大量参考论文。