Jul, 2015

基于平方和证明的张量主成分分析

PDF
TL;DR研究了一个针对张量主成分分析问题的统计模型，通过基于四次幂和松弛的舍入算法，证明了随机噪声张量的种植向量可以在高概率下被回收，还证明了四次幂和松弛在一定程度下是不起作用的，研究并利用了额外的问题结构来求解我们的平方和松弛。
tensor principal component analysisstatistical modelsum-of-squares methodconvex relaxationsmaximum likelihood estimation
发现论文，激发创造
  • 一种张量 PCA 的统计模型

    本文针对任意阶数的大型张量，从信息论和概率论角度出发，讨论了单峰（或秩一加噪声）模型下的主成分分析问题。并使用张量展开、幂迭代和信息传递等多项式时间估算算法分析了这一问题的可行性，阐述了张量幂迭代的初期化和运用附加侧信息推导良好估算的条件。

    Nov, 2014

  • 多项式时间的带有平方和项的张量分解

    本文基于平方和方法给出了用于张量分解的新算法，结果改进了多个问题的运行时间，包括对超完备三元组分解和具有常数相对稀疏度的超完备字典的学习等问题的算法，同时首次在平滑分析模型中给出了超完备四元组分解的稳健性分析。而此分析的关键因素在于在由平方和松弛解导出的矩阵时刻中建立小的谱间隙，为了使此分析成为可能，本文将最大熵约束的谱同构加到平方和松弛约束上。

    Oct, 2016

  • 稀疏主成分分析的平方和下界

    本文研究使用凸松弛法解决高维机器学习问题时，统计与计算的权衡。对稀疏主成分分析（Sparse PCA）问题和 Sum-of-Squares（即 Lasserre / Parillo）凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况，为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限，说明它们存在困难问题。

    Jul, 2015

  • 基于平方和证明的快速谱算法：张量分解和种植稀疏向量

    研究了两个基于机器学习应用中的问题：在随机线性子空间中恢复种植稀疏向量的问题以及分解随机低秩超完备三阶张量的问题。通过分析和受到二次和方法的启发，提出了新的算法，其可以在更快的时间内实现与二次和方案相似的保证

    Dec, 2015

  • 基于平方和方法的字典学习和张量分解

    本文提出了一种新的方法用于词典学习即稀疏编码的问题，其中，算法能够在噪声张量分解方面解决任意泊松（Poisson）噪声情况，并且本算法同样适用于具有更高的稀疏度，并且基于一个使用和分析半正定规划的 Sum of Squares 层次结构的新方法。

    Jul, 2014

  • 张量补全的谱算法

    该研究提出了基于展开的新方法，其中一个应用是特征空间估计。研究者针对张量完成问题，提出了两种方法，一种是采用 SOS 方法，但不适合处理大规模问题；另一种是采用展开或者矩阵分解方法，在解决三阶张量问题时性能和 SOS 方法相当。

    Dec, 2016

  • 具有平方和形式的张量精确完成

    本研究使用最优的多项式算法，仅依靠少量随机观察数据完成张量解析，并将通过球上的正交全局极值证明的事实证明到可以在和方法证明系统内进行。

    Feb, 2017

  • 舍入平方和松弛问题

    通过转换一个分布映射算法为一个近似解，我们提出了一个通过利用半正定规划松弛和 SOS 证明系统之间的联系来舍入 SOS 松弛的一般方法，并应用于 3 个已知问题的改进，分别是：低次多项式最大值问题、小集合扩展问题以及恢复一个种植稀疏向量的多项式时间算法。

    Dec, 2013

  • 使用平方和算法分解超完备的三阶张量

    使用 sum-of-squares 层次结构的思想，我们提供了第一个几乎多项式时间复杂度的算法，可以在分解随机 3 阶张量时，将秩提高到 $n^{3/2} / extrm {polylog} n$。我们还提出了一种检验低秩张量的 injective norm 的多项式时间复杂度算法，并证明了这个算法的正确性。

    Apr, 2015

  • 稀疏主成分分析的最优解

    本论文提出了一种基于协方差矩阵的稀疏主成分分析方法，采用半正定松弛和贪心算法求解，可以适用于诸如子集选择和稀疏恢复等领域，并能在人工和生物数据等实验数据中提供全局最优解。

    Jul, 2007