Jul, 2018

基于良好条件基础的 Minkowski $p$- 范数流式和分布式摘要

PDF
TL;DR本文研究了适用于不同的 lP 范数的近似线性代数问题，提出了一种同时适用于每个 p ≥ 1 的确定性算法，并将其应用于多种问题，如 lP 回归，逐元素 l1 低秩逼近和近似矩阵乘法。
发现论文，激发创造
  • 矩阵 p - 范数的近似计算

    该研究考虑了如何计算矩阵范数，给出了基于固定点迭代的有效算法，并证明了在某些参数范围内，该问题是 NP 难的。

    Jan, 2010

  • 指数随机变量的子空间嵌入和 Lp 回归

    本文从子空间嵌入的角度出发，提出了一种构造常数扭曲率子空间嵌入的新方法，并将其应用于线性回归问题以及分布式计算中。

    May, 2013

  • 一种蕴含 Schatten-$p$ 范数的凸代理函数

    本文通过建立 Schatten-p norm 与 factor matrices 中的 Schatten-p1 和 Schatten-p2 norm 之间的等价性，进一步扩展到多个因子矩阵中，表明其所有的因子 norm 都可以是任意 p 的凸光滑的，从而利用凸性提出加速的 proximal alternating linearized minimization algorithm，并在合成和实际数据集上通过矩阵补全任务展示了其优越性能。

    Nov, 2016

  • 矩阵近似乘法及其在线性嵌入方面的应用

    该论文研究了计算两个实矩阵乘积的近似算法，提出了核秩的概念，并应用于线性低维嵌入中，使得任何核秩有界的欧几里得点集能够在独立于输入维度的投影空间上实现加性误差保证。

    Mar, 2014

  • 网络中稀疏正则化秩最小化：算法与应用

    本文发展了使用分布式算法解决低秩矩阵加上压缩矩阵与稀疏矩阵乘积的分离任务，建立了分布式稀疏正则化秩最小化的算法框架，其中采用核范数和 l1 范数用作所需矩阵的秩和非零条目数的替代，使用交替方向乘法的分离算法来最小化经过采样和压缩的数据的秩和 nonzeros，从而解决了一些网络优化问题。

    Mar, 2012

  • 应用于网络图的向量摘要的核心集

    提供一种确定性数据汇总的算法来表示用户的好友群体和活动摘要，这可以被用于从 GPS 轨迹或信息交换来识别会议或好友组，并可以标识邻接矩阵中的重要节点。

    Jun, 2017

  • 可扩展的算法用于易处理的 Schatten 准范数最小化

    本文针对大规模问题，定义了容易处理的 Frobenius / 核混合和双核范数，通过更新两个较小的因子矩阵，设计了两种代表矩阵完成问题的高效近端交替线性化最小化算法，证明它们优于现有算法，具有更好的收敛性和性能保证。

    Jun, 2016

  • 低秩矩阵值 Chernoff 界和近似矩阵乘法

    本文提出了一种利用两种不同抽样方法进行矩阵乘法，以逼近具有谱范数的矩阵，从而得出理论上的界限。

    May, 2010

  • 流式大数据矩阵和张量的子空间学习和插补

    论文提出了一种基于 rank minimization 算法的在线优化方法，通过追踪低维度子空间、揭示潜在结构以及使用核范数正则化来实现低维矩阵数据和低秩张量数据的缺失值插补，模拟测试显示该方法在数据明显含噪、不完整的情况下表现突出。

    Apr, 2014

  • 计算近似的 ℓp 敏感度

    近期在降维回归任务中引入了敏感性的概念，提供了通过子采样移除低敏感性数据点后的近似质量的可证明保证。本文提供了计算给定矩阵的相关汇总统计量和近似敏感性的高效算法，分别针对不同的 Lp 范数进行了泛化，并通过实验表明，实际数据集的敏感性远远小于理论预测，展示了实际数据集的低内在有效维度。

    Nov, 2023