Sep, 2012

求解二次测量稀疏信号恢复问题的凸规划方法

PDF
TL;DR本文研究含二次方程的稀疏解的凸优化计算方法，证明了对于下限为 O (log n (m)^(1/2)) 的朴素凸松弛方法是准确的。
quadratic equationssparse solutionconvex optimizationunderdetermined systemnaive convex relaxations
发现论文，激发创造
  • 通过非凸优化破解样本复杂度壁垒的二次测量结构信号恢复

    本文针对 $m<<n$ 的欠定情况，在优化变量上施加先前的结构信息，将恢复问题形式化为非凸优化问题，并证明了在任何不变约束集下，投影梯度下降收敛于未知信号的线性速率，这为此数据贫瘠的场景提供了第一个可证实的算法，为理解约束非凸优化启发了强有力的工具，其数学结果为数据驱动的相位成像系统开辟了一种新的方向。

    Feb, 2017

  • 通过凸松弛：傅里叶和高斯测量的稀疏重建

    研究如何通过几个稀疏信号线性测量（与一些固定向量的内积）的结果精确重构出稀疏的信号，并考虑了两种测量方法：高斯测量和傅里叶测量。通过几何函数分析和 Banach 空间中的随机性证明了这两种方法的最佳测量数量。

    Feb, 2006

  • PhaseLift: 通过凸规划从幅度测量中精确稳定地恢复信号

    利用随机取样的向量进行半定规划中的痕范数最小化，证明了可以通过凸编程技术解决组合相位恢复问题，且该方法对加性噪声具有鲁棒性。

    Sep, 2011

  • 解二次方程组时的局部凸性

    本文介绍了一种可行的方法，利用梯度下降并结合谱初始化逼近正半定秩为 r 的矩阵 X X^T，并证明了在高斯分布下均匀采样 m >= Cnrlog^2 (n) 个样本时，可以在有很高概率下找到初始点，从而使梯度下降能收敛到正确结果。

    Jun, 2015

  • 独立随机线性测量下结构化信号的凸恢复

    本文基于凸规划方法，从独立随机线性测量中恢复结构信号，为采样复杂度提供类似于标准高斯测量的界限，并发掘该方法的实际应用，包括一项关于痕范数最小化的相位恢复分析。

    May, 2014

  • 关于最优化测量数量的块稀疏信号重构

    研究了压缩感知中稀疏解的求解问题，提出一种基于 L1 - 范数和半定规划的解法，对于块稀疏向量能找到最稀疏的解，该方法具有多项式时间复杂度。

    Mar, 2008

  • 基于半定规划的压缩相位恢复从平方输出量测中

    本文研究了在输出测量值缺失相位信息的情况下，如何使用半定规划精确恢复稀疏信号。我们通过提出的升维技术，证明了只需采样频率足够高，即可通过求解简单的半定规划来恢复稀疏信号，从而扩展压缩感知技术的应用范围。

    Nov, 2011

  • 线性规划下的一比特压缩感知

    本文通过随机线性测量得到的 O (s log^2 (n/s)) 个标志位，利用线性规划，从稀疏向量中精确恢复出 s-sparse 向量 x，进而将结果推广到了近似稀疏的向量 x。文章以解决随机超平面填充的等效几何问题为基础，并且该方法几乎是最优解。

    Sep, 2011

  • 1 位压缩感知与稀疏逻辑回归的鲁棒性：凸规划方法

    论文使用单一的凸优化程序分别对于噪声的一位非压缩感知和稀疏二项回归进行精确估计。作者展示，使用简单的凸优化程序，可以从单位比特量度中精确地估计在 R ^ n 中的 s 稀疏信号。

    Feb, 2012

  • 近似稀疏恢复：优化时间和测量

    研究如何构建稀疏恢复系统，以最小化测量矩阵的数量和解码算法的运行时间，给出了一个具有优秀性能的系统，其中测量矩阵的数量与下界相匹配，且解码时间为下界的对数倍。同时还考虑了编码时间、更新时间、算法的鲁棒性和稳定性。

    Dec, 2009