基于列的最优低秩矩阵重构

Apr, 2011

Optimal Column-Based Low-Rank Matrix Reconstruction

Venkatesan Guruswami, Ali Kemal Sinop

TL;DR证明对于任意实值矩阵 X，在正整数 r≥k 的情况下，存在 X 的 r 个列的子集，将 X 投影到其中一个列的线性组合中，得出的结果将是 Frobenius 范数下的 X 的最佳秩 - k 逼近的一个近似值等于 sqrt ((r + 1)/(r-k +1))。并提出一个确定性算法可在 O (r n m^ω log m) 时间内找到这样的列的子集，其中 ω 是矩阵乘法的指数。同样，我们提供了一种更快的随机算法，可在 O (r n m^2) 时间内进行运算。

Abstract

We prove that for any real-valued matrix $X \in \R^{m \times n}$, and positive integers $r \ge k$, there is a subset of $r$ columns of $X$ such that projecting $X$ onto their span gives a $\sqrt{\frac{r+1}{r-k+1}}$-approximation to best rank-$k$ approximation of $X$ in →

real-valued matrix frobenius norm rank-k approximation subset selection deterministic algorithm

发现论文，激发创造

基于列的矩阵重构的近最优解

该研究论文考虑使用矩阵的列进行低秩重构，并提出了渐近最优的谱范数和 Frobenius 范数重构算法。

Mar, 2011

列子集选择问题的改进近似算法

本文通过一个新的两阶段算法，随机选择行矩阵中相应基于前 K 大的奇异空间的概率分布，又应用确定性列选择程序，以 Frobenius 范数和谱范数为衡量指标，分别得到 A 和其最佳秩 K 近似之间的较优边界

Dec, 2008

快速矩阵排名算法与应用

本文介绍了一种随机算法来计算矩阵的秩，可以在线性时间内找到一组线性无关的列，并解决了动态矩阵更新问题。这种方法可以有效地应用于数值线性代数、组合优化和动态数据结构中。

Mar, 2012

几乎验证时间内的矩阵完成

我们提供了一个解决低秩矩阵完成问题的新框架，通过聚合涉及观测的回归问题的解来将矩阵 M 完成，并改进了之前已知的算法的样本复杂度和运行时间。

Aug, 2023

广义秩受限矩阵逼近

本文探讨矩阵的秩约束 Frobenius 范数逼近问题，即对于 $m$ 乘 $n$ 矩阵 $A$，求出秩不超过 $k$ 的矩阵。

Mar, 2006

低秩核矩阵近似的尖锐分析

本文研究了在正定核框架下的监督学习问题，提出了基于随机矩阵列采样的核矩阵低秩近似方法，此方法可以在 sub-quadratic 的时间复杂度内有效解决核矩阵计算问题，同时保持预测性能不变。

Aug, 2012

从部分条目恢复矩阵

本文研究如何从观测到的随机稀疏矩阵子集中重建一个秩较低的随机矩阵，提供相应的算法并给出一些误差保证以及时间复杂度估计，并得到一些稀疏随机矩阵谱的推广结果。

Jan, 2009

稳定秩下的最优近似矩阵乘积

用子空间嵌入保证黑盒方式证明，通过降维映射可实现近似矩阵乘法的谱范数保障，其中降维映射具有 O（~r/ε^2）行，且优于以前的工作 [MZ11，KVZ14]，对于任何混淆的降维映射也是最佳的。

Jul, 2015

从一阶测量中恢复低秩矩阵

本文研究了通过核范数最小化从采样测量中恢复 Hermite 低秩矩阵的问题，其中测量是 Frobenius 内积形式的随机秩一矩阵，我们导出了确保成功恢复矩阵所需的测量数的界限，同时证明了测量扰动的鲁棒性和近似 4 - 设计对相位恢复的一般性限制。

Oct, 2014

列子集选择、矩阵分解和特征值优化

提出了一种基于随机列抽样的多项式时间算法，用于选择具有良好谱特性的矩阵子集，具有较高的计算效率和实用价值，并结合 Grothendieck 因子分解构造了一种新的近似算法，以计算矩阵的（无穷大，1）范数。

Jun, 2008