May, 2011

无约束 L_2-L_p 最小化的复杂度

PDF
TL;DR本文研究非受限情况下的 $L_2$-$L_p$ 最小化问题，并展示了这个问题的各种吸引人的特性，同时表明 $L_q$-$L_p$ 最小化问题是强 NP 困难问题，但可以通过精心选择参数获得所需的稀疏性，这些结果为凸规则化优化问题的研究和应用提供了新的理论洞察。
发现论文，激发创造
  • 迭代加权最小化方法：$l_p$ 正则化非约束非线性规划

    本文提出了一种基于 l_p 正则化无约束极小化问题的新方法，包括通过闭形式求解每个子问题的 IRL1 和 IRL2 变体，以及这些方法的收敛性分析和基于唯一的 Lipschitz 连续的 ε- 近似的新 IRL1 方法。我们的计算结果表明，该方法对于目标函数值和 CPU 时间通常比现有的 IRL1 方法更稳定。

    Sep, 2012

  • Lp 回归的采样算法和核集

    该论文提出了一个有效的两阶段抽样算法来解决 Lp 回归问题，包括构建核心集合、采样等方法，并且在算法的证明过程中提出了两个值得研究的概念：条件良好的基和子空间保留采样。

    Jul, 2007

  • 正则化与小球方法 II：复杂度相关的错误率

    研究基于正则化函数的凸函数估计的性质，给出 $L_2$ 估计误差速率的界限，包括 True Model 的复杂度，应用于不同的正则化函数，结果适用于学习理论框架。

    Aug, 2016

  • 基于 Lp 范数最小化的压缩感知典型重构限制

    本文探讨了如何利用 L_p-norm 等方法在限制非零元素个数的条件下，通过线性转换的约束来重构出一个 N 维向量 x.

    Jul, 2009

  • 最小二乘规则化的零范数解析及其全局极小值的唯一性

    本文分析了关于采用矩阵解决求解目标问题的本质方法，提出了可以帮助解决数值方案算法新思路的理论贡献，并以多种方式探讨了矩阵求解模型。

    Apr, 2013

  • 避免非凸正则化问题的严格鞍点

    我们引入了 $l_p$ 正则化函数的严格鞍点性质，并提出了一种迭代重新加权的 $l_1$ 算法来解决 $l_p$ 正则化问题。该算法只能收敛到局部极小值点，严格鞍点性质在这些稀疏优化问题中是普遍的，这些分析以及提出的算法可以轻松扩展到一般的非凸正则化问题。

    Jan, 2024

  • 矩阵 p - 范数的近似计算

    该研究考虑了如何计算矩阵范数，给出了基于固定点迭代的有效算法，并证明了在某些参数范围内，该问题是 NP 难的。

    Jan, 2010

  • 有约束极小极大优化的复杂性

    本文通过分析优化问题的计算复杂性，阐明了一系列非凸非凹目标函数的约束极值优化问题存在的困难，同时证明了该问题在 Nemirovsky-Yudin 模型中的难度，这与最小化问题在同样设置下可以使用 Projected Gradient Descent 进行近似局部最小值的行为形成了对比。

    Sep, 2020

  • 出租车空间中的欧几里得：配备平滑化 l1/l2 正则化的稀疏盲反卷积

    本研究提出了一种基于光滑逼近的 l1/l2 函数的新罚函数，并开发了一种基于 proximal 的算法来解决涉及此函数的变分问题，并得出了理论收敛结果。通过与最近的交替优化策略进行比较，我们展示了我们方法在地震数据盲解卷积中的有效性。

    Jul, 2014

  • 低秩矩阵优化的非凸几何

    本文针对两个广泛使用的最小化问题：凸函数最小化问题和加上核范数的凸函数最小化问题，提出使用低秩分解和替代核范数的方法来加速求解问题，并证明其可以在全局范围内找到最优解。

    Nov, 2016