压缩感知与矩阵填充是信号处理与重构的两个方面。虽然它们所处理的具体问题是不同的，但是相互之间有着紧密的联系。在压缩感知理论中的一个核心问题是求解l0范数意义下的最小化问题，它的目的是在欠定方程组无穷个解中选择最稀疏的一个解来构造原始信号(向量)。矩阵填充的目的是只运用原始矩阵中一部分元素来构造一个低秩矩阵去逼近原始矩阵。设计求解这两个重构问题的算法一直是压缩感知与矩阵填充的重点。本论文研究压缩感知与矩阵填充的重构算法，其主要工作与创新如下：　　(1).本论文首先分析压缩感知的软阈值算法、硬阈值算法、稳固阈值算法与拟软阈值算法。通过对拟软阈值算法进行参数化，得到参数化拟软阈值算法。再对参数化拟软阈值算子的参数进行迭代更新，得到变参数拟软阈值算法。证明了这个算法的收敛性，并用数值实验表明变参数拟软阈值算法能有效提高信号重构的精度。　　(2).本论文提出了压缩感知的变基正交匹配追踪算法。给出了迭代原理、迭代格式。通过一维仿真的数值实验表明变基正交匹配追踪算法能提高信号的恢复的精度与重构概率。　　(3).通过分析矩阵填充的软阈值算法、硬阈值算法与拟软阈值算法，本论文提出了矩阵填充的参数化拟软阈值算法与变参数拟软阈值算法。证明了这些算法的收敛性，数值实验表明参数化拟软阈值算法与变参数拟软阈值算法能提高矩阵填充的精度。　　(4).分析了矩阵填充问题的正交秩1矩阵追踪算法，然后将这个算法推广为低秩逼近追踪算法。将正交秩1矩阵追踪算法中每一次迭代步只取一个秩1矩阵作为基矩阵进行改进，即在每次迭代步中选取多个秩1矩阵为基矩阵，使得迭代次数降低。进一步分析了低秩逼近追踪算法比原来的正交秩1矩阵追踪算法具有更低的计算复杂度，并证明了该算法是线性收敛的。最后，进行数值实验，数值结果表明新的低秩逼近追踪算法对图像恢复与推荐系统是有效，而且计算用时少。