近似线性时间的半随机稀疏恢复
研究压缩感知的一般框架,提出了一种非线性测量的自然推广方法,并证明了通过这些测量可以有效地计算和恢复稀疏信号。提出了三种算法,其中包括一种称为广义 OLS 的贪心算法,以及两种硬和软阈值迭代算法的自然推广方法,并证明了这些算法对于基于 Lipschitz 扰动的 RIP 矩阵的非线性测量具有强的恢复保证。
Nov, 2013
本文旨在设计一个在线学习算法,使其具有次线性失望成本并且具有计算效率,以适应在线稀疏线性回归问题。通过利用数据矩阵满足受限等距性质的假设,针对两个问题变体,证明了这个假设可以导致计算效率高的在线学习算法。第一个变体中,真实标签根据带有加性高斯噪声的稀疏线性模型生成,而在第二个变体中,真实标签由对手选择。
Jun, 2017
本文考虑了高维设置下的稀疏向量,研究在测量速率和样品的信噪比为有限常数的情况下,稀疏模式估计的误差比例将为常数分数,并且通过与现有可实现界的比较,建立了在比例误差和信噪比的功能下的范围上限。
Feb, 2010
本文介绍了稀疏信号恢复的两种算法方法:几何和组合。我们提出了一种统一这两种方法的新方法,通过高质量不平衡扩展器的邻接矩阵来推广受限等距性质的概念,并展示了新的测量矩阵构造和算法,比先前的算法在测量数量或噪声容忍度上具有更好的表现。
Apr, 2008
研究如何构建稀疏恢复系统,以最小化测量矩阵的数量和解码算法的运行时间,给出了一个具有优秀性能的系统,其中测量矩阵的数量与下界相匹配,且解码时间为下界的对数倍。同时还考虑了编码时间、更新时间、算法的鲁棒性和稳定性。
Dec, 2009
本文探讨了应用于无惩罚最小二乘回归问题的梯度下降方法的隐式正则化方案,旨在从线性测量的过少的系统中重构出一个稀疏信号,考虑到受限等距假设,我们展示了有一定参数下,预设好的初始化、步长和停机时间能给出一个在统计和计算上都是优的算法,可以在费用与读取 poly-logarithmic 因子的数据一样的代价下,实现极小化率。除了最小化控制,我们还展示了当信噪比足够高时,算法会适应实例的困难度并产生一个与维度无关的率。实现算法的关键是一个逐渐增加的步长方案,根据对真实解的精细估计进行适应。我们通过数值实验验证了我们的发现并将我们的算法与显式 Λ1 惩罚进行了比较。从难实例到容易实例,我们看到我们的算法经历了一个相变,最终与具有真正的支持知识的最小二乘拟合器匹配。
Sep, 2019
本研究探讨通过非凸优化从线性测量(即矩阵感知)中估计低秩矩阵的问题,并建议了一种有效的随机方差减少梯度下降算法来解决此问题。我们的算法适用于有噪声和无噪声的情况。在有噪声的情况下,我们证明了该算法在最小化统计误差方面以线性速率收敛于未知低秩矩阵。在无噪声的情况下,我们的算法保证线性收敛于未知低秩矩阵,并在最优采样复杂度下实现了精确恢复。值得注意的是,我们提出的算法的总计算复杂度(定义为迭代复杂度乘以每次迭代时间复杂度)低于基于梯度下降的最新算法。用合成数据的实验证明了该算法优于现有算法。
Jan, 2017
研究利用具有独立同分布和均匀有界行以及具有非平凡协方差结构的结构化随机测量矩阵的稀疏恢复。因为这类矩阵是从边界瑞格系统的随机采样得来的,并且广义化了随机部分傅立叶矩阵。该结果改进了目前对这种随机矩阵的零空间和限制保持特性的可用结果,并将其应用于证明 CORSING 方法的新绩效保证。
May, 2020
研究了基于 Nesterov 的对偶平均算法的随机优化算法,在预期损失是强凸的且最优解是(近似)稀疏的问题上进行优化,证明了在局部 Lipschitz 损失下,在 T 轮迭代后,我们的解决方案的误差最多为 O((slogp)/T),并确立了我们的收敛率是最佳的,且在数值模拟中通过对最小二乘回归问题进行几个基准线的比较,证实了我们方法的有效性。
Jul, 2012