基于平方和证明的快速谱算法:张量分解和种植稀疏向量
本文基于平方和方法给出了用于张量分解的新算法,结果改进了多个问题的运行时间,包括对超完备三元组分解和具有常数相对稀疏度的超完备字典的学习等问题的算法,同时首次在平滑分析模型中给出了超完备四元组分解的稳健性分析。而此分析的关键因素在于在由平方和松弛解导出的矩阵时刻中建立小的谱间隙,为了使此分析成为可能,本文将最大熵约束的谱同构加到平方和松弛约束上。
Oct, 2016
使用 sum-of-squares 层次结构的思想,我们提供了第一个几乎多项式时间复杂度的算法,可以在分解随机 3 阶张量时,将秩提高到 $n^{3/2} / extrm {polylog} n$。我们还提出了一种检验低秩张量的 injective norm 的多项式时间复杂度算法,并证明了这个算法的正确性。
Apr, 2015
本文提出了一种新的方法用于词典学习即稀疏编码的问题,其中,算法能够在噪声张量分解方面解决任意泊松(Poisson)噪声情况,并且本算法同样适用于具有更高的稀疏度,并且基于一个使用和分析半正定规划的 Sum of Squares 层次结构的新方法。
Jul, 2014
该研究提出了基于展开的新方法,其中一个应用是特征空间估计。研究者针对张量完成问题,提出了两种方法,一种是采用 SOS 方法,但不适合处理大规模问题;另一种是采用展开或者矩阵分解方法,在解决三阶张量问题时性能和 SOS 方法相当。
Dec, 2016
研究了一个针对张量主成分分析问题的统计模型,通过基于四次幂和松弛的舍入算法,证明了随机噪声张量的种植向量可以在高概率下被回收,还证明了四次幂和松弛在一定程度下是不起作用的,研究并利用了额外的问题结构来求解我们的平方和松弛。
Jul, 2015
本文研究使用凸松弛法解决高维机器学习问题时,统计与计算的权衡。对稀疏主成分分析(Sparse PCA)问题和 Sum-of-Squares(即 Lasserre / Parillo)凸松弛法进行了探究。通过研究发现基于次数 - 4 的 SoS 算法不能改善计算次数为 k² 的情况,为这种强大的凸松弛算法族中的一部分问题建立了平均情况下的下限,说明它们存在困难问题。
Jul, 2015
在 “可能但艰难” 的稀疏主成分分析中,我们使用亚指数时间算法的能力来探索稀疏度和恢复时间的平滑权衡,提供了一种新的演变家族,并对低阶似然比进行分析,从而证明了我们算法所实现的权衡是最优的。
Jul, 2019
通过平滑分析模型,本文提出了一种针对高度过完备情况(秩多项式于该张量维度)的张量分解的有效算法,且该算法具有鲁棒性,即使输入存在逆多项式误差,其表现依然可靠。该算法的线性独立性结果为我们在学习过程中应用张量方法提供了方便,为多视图模型和轴向高斯混合等学习问题的研究提供了更多的组件维度。
Nov, 2013
研究了张量恢复中的样本量要求,提出梯度下降算法结合谱方法来重建低秩高阶张量,事实证明我们的方法在保证高概率的情况下只需要 O (r^7/2*d^3/2*log^7/2 (d)+r^7*d*log^6 (d)) 个样本,且可以很好地处理低秩多线性张量,相对于其他方法具有高效易用性的优点。
Feb, 2017