稀疏约束下线性反问题的加速投影梯度方法
提出了一种显式算法,用于最小化带有不可分离 L1 项的 L1 正则化最小二乘函数。对于每个迭代步骤,该算法需要四个矩阵向量乘法和单个简单的投影,并证明了收敛性和函数的 1/N 收敛速率。同时,该算法可以处理其他基于 L1-norm 以外的凸非分离度量,方法是用简单的接近算子代替投影。
Apr, 2011
该研究考虑线性反问题,其中解被假定在任意预先分配的正交基上具有稀疏展开,利用加权 l^p 准则对系数进行正则化,提出了一种迭代算法计算对应的正则化解,并证明了算法的收敛性以及该方法的一些潜在应用。
Jul, 2003
本文提出了利用一种启发式策略来解决稀疏恢复和压缩感知中的 $\ell_1$- 正则化最小二乘问题。该方法能够获得全局几何收敛速率,其迭代复杂度为 $O (\log (1/\epsilon))$。
Mar, 2012
该篇文章提出了针对无限维希尔伯特空间中线性算子方程迭代软阈值算法的统一方法,并在广义梯度方法框架下提出了新的收敛分析。主要结果表明,只要底层算子满足所谓的有限基数可逆性质或最小值具有所谓的严格稀疏模式,该算法将以线性速率收敛。此外,该技术还可用于建立相关方法的线性收敛性,如联合稀疏迭代阈值算法和加速梯度投影方法。
Sep, 2007
本文探讨了应用于无惩罚最小二乘回归问题的梯度下降方法的隐式正则化方案,旨在从线性测量的过少的系统中重构出一个稀疏信号,考虑到受限等距假设,我们展示了有一定参数下,预设好的初始化、步长和停机时间能给出一个在统计和计算上都是优的算法,可以在费用与读取 poly-logarithmic 因子的数据一样的代价下,实现极小化率。除了最小化控制,我们还展示了当信噪比足够高时,算法会适应实例的困难度并产生一个与维度无关的率。实现算法的关键是一个逐渐增加的步长方案,根据对真实解的精细估计进行适应。我们通过数值实验验证了我们的发现并将我们的算法与显式 Λ1 惩罚进行了比较。从难实例到容易实例,我们看到我们的算法经历了一个相变,最终与具有真正的支持知识的最小二乘拟合器匹配。
Sep, 2019
本文论述了解决线性反问题的优化问题的尖锐时间 - 数据权衡,重点研究了一个最小化普通最小二乘目标的限制条件问题,我们提出了一个统一的收敛分析方法,针对各种随机测量阵列,依据所选择的惩罚函数所对应的结构复杂度,尖锐地表征了收敛速率。结果适用于凸和非凸约束条件,并表明在这些设置中即使最小二乘目标函数不是强凸性,在这些设置中也可以达到线性收敛速率。当我们特定于高斯测量时,我们的结果表明,当测量次数仅是恢复所需信号的最小次数的 4 倍(即所谓的相位转换)时,就会出现这种线性收敛。我们还在相位转换点的上方精确地实现了一个更慢但几何的收敛速率。广泛的数值结果表明,所得到的速率与实际性能完全匹配。
Jul, 2015
本文提出一种有效的算法来解决图像恢复应用中的约束问题,包括去卷积和从压缩观测中重建图像,使用总变差或小波(或更一般的框架)正则化。该算法属于增广 Lagrange 方法的范畴,并表现出在一定条件下具有收敛性。本文的结果表明,所提出的算法在图像恢复领域中具有最先进的技术水平。
Dec, 2009
本文提出了一种称为平滑近端梯度方法的通用优化方法,它能够解决带有平滑凸损失和广泛结构稀疏诱导罚款的结构稀疏回归问题,通过 Nesterov 的一般平滑技术实现了比标准一阶法更快的收敛速度,比大多数广泛使用的内点法更可扩展。
Feb, 2012
本文提出了一种基于近端梯度方法(G-ISTA)的 L1 正则化协方差矩阵估计方法,它具有线性收敛率和 O (log e) 迭代复杂度,能够有效地用于产生稀疏逆协方差估计量,并探讨了其特性及在数值测试中的表现。
Nov, 2012