矩阵 p - 范数的近似计算
研究线性算子 2->q 范数的计算复杂性,该范数定义为 ||A||_{2->q}=sup_v||Av||_q/||v||_2,以及这个问题与量子信息理论和 Khot 的唯一游戏猜想 (UGC) 的问题之间的联系。
May, 2012
本文通过建立 Schatten-p norm 与 factor matrices 中的 Schatten-p1 和 Schatten-p2 norm 之间的等价性,进一步扩展到多个因子矩阵中,表明其所有的因子 norm 都可以是任意 p 的凸光滑的,从而利用凸性提出加速的 proximal alternating linearized minimization algorithm,并在合成和实际数据集上通过矩阵补全任务展示了其优越性能。
Nov, 2016
本文研究了适用于不同的 lP 范数的近似线性代数问题,提出了一种同时适用于每个 p ≥ 1 的确定性算法,并将其应用于多种问题,如 lP 回归,逐元素 l1 低秩逼近和近似矩阵乘法。
Jul, 2018
本文针对大规模问题,定义了容易处理的 Frobenius / 核混合和双核范数,通过更新两个较小的因子矩阵,设计了两种代表矩阵完成问题的高效近端交替线性化最小化算法,证明它们优于现有算法,具有更好的收敛性和性能保证。
Jun, 2016
本文研究了距离矩阵的低秩近似,证明了在任何底层距离度量下,均可以在亚线性时间内实现加性误差的低秩近似,并发展了一种基于投影 - 成本保持抽样的递归算法。同时,在一般情况下,相对误差逼近是不可能的,即使允许二标准解决方案。此外,如果 P = Q 并且 d 是欧几里得平方距离,则可以在亚线性时间内找到相对误差的二标准解决方案。
Sep, 2018
本文研究了非负张量的 l^p 奇异值问题,证明了弱不可约和不可约非负张量的普通 Perron-Frobenius 定理,并提供了最大奇异值的 Collatz-Wielandt 特征描述。此外,我们提出了更高阶幂法来计算最大奇异向量,并证明其具有渐近线性收敛速度。
Mar, 2015
研究子空间草图问题,通过构建一个小空间数据结构压缩给定矩阵,讨论其压缩方案和所需存储空间以及相应的下界,探讨其在矩阵乘积中的应用,展示了对内积基于任意数构建数据结构的不可行性以及 l1 奇异值分解的不同情况下的空间复杂度变化。
Apr, 2019
本文研究非受限情况下的 $L_2$-$L_p$ 最小化问题,并展示了这个问题的各种吸引人的特性,同时表明 $L_q$-$L_p$ 最小化问题是强 NP 困难问题,但可以通过精心选择参数获得所需的稀疏性,这些结果为凸规则化优化问题的研究和应用提供了新的理论洞察。
May, 2011