Nov, 2012

通过双重随机投影恢复最优解

PDF
TL;DR本文提出了一种名为 Dual Random Projection 的简单算法，通过将高维数据映射到低维子空间来减少计算成本，使用低维优化问题的对偶解来恢复原始优化问题的最优解，并分析了算法的理论依据。
random projectiondata classificationlow-dimensional subspaceoptimization problemdual random projection
发现论文，激发创造
  • 基于随机投影的素描重建：一种可证明的用于大规模高维数据的恢复算法

    本文从优化的角度研究素描技术，提出了加速 Hessian 素描和双重随机投影的方法，并通过迭代对原始和对偶公式进行素描来解决大规模问题。在合成和真实数据集上进行了广泛的实验验证。

    Oct, 2016

  • 自适应随机子空间中的高维优化

    提出了一种新的高维随机优化方法，将坐标下降法推广到随机子空间，证明了使用自适应采样策略的随机子空间可以显著优于最近文献中常见的盲目采样方法，可以通过相关随机矩阵集合有效生成自适应子空间；在具有不同谱衰减的数据矩阵上验证了该方法在机器学习问题中的速度优势，包括逻辑回归、带随机卷积层的核分类和具有修正线性单元的浅神经网络。

    Jun, 2019

  • 大规模回归的随机投影

    本文探讨了随机投影在线性回归问题中的应用，旨在降低计算成本，结合最小二乘回归可产生类似岭回归和主成分回归的恢复效果，并探讨了多次随机投影平均的可能改进。

    Jan, 2017

  • 基于随机投影的降维技术综述

    本文总结了基于随机投影的不同方法的使用情况，旨在帮助实践者为其特定应用选择合适的技术，并列举了各种方法的优缺点，并为研究人员提供进一步的参考，以开发新的基于随机投影的方法。

    Jun, 2017

  • 具有尖锐保证的凸规划的随机草图

    该研究探讨了使用随机投影进行维度降低的方法来近似解决具有凸性质的问题，在计算有限的情况下具有广泛的应用，同时还可以提高隐私保护和降低存储和计算成本。研究证明了该方法的近似比率可以用约束集合的几何特性来界定，对于一类广泛的随机投影，其投影结果数据矩阵的维度相对于原始问题的维度相对较小，该理论还与降噪、压缩感知等领域有关系。

    Apr, 2014

  • 随机投影实验

    该研究阐述了随机投影的应用，作为降维技术来学习高斯混合模型，并通过实现合成和真实数据的广泛实验来说明此方法的可行性。

    Jan, 2013

  • 通过随机线性投影逼近低维流形上的点

    本文介绍了一种基于流形的信号恢复算法，该算法使用少量线性测量就可以非常精确地重构给定数据点，对外部维度不敏感，同时提供一致的逼近保证。

    Apr, 2012

  • 随机投影的精确表达式：低秩逼近与随机牛顿

    利用随机矩阵的谱分析最新进展，我们开发了一种新的技术，提供了随机投影矩阵的期望值的确切表达式，这些表达式可以用来表征多种常见的机器学习任务中的降维性能，包括低秩估计和迭代随机优化等。我们的结果适用于多种流行的草图方法，包括高斯和 Rademacher 草图，结果表明，我们推导出的表达式反映了这些草图方法的实际性能，甚至体现了较低阶效应和恒定因子。

    Jun, 2020

  • 通过投影消除偏差的主要公平性

    在算法数据分析中，通过随机投影到 “公平” 子空间来减少数据中的偏差，我们将这种方法应用于最密子图问题，理论上和实验上都可以恢复一个几乎最优、公平、稠密的子图，并通过匹配逼近上界展示该问题的 NP - 难度特性。

    May, 2019

  • 鲁棒子空间恢复概述

    此论文为关于鲁棒性子空间恢复的工作作为介绍。该工作重点介绍了现有方法的优缺点以及该领域中未解决的问题，其目标是在可能被离群值破坏的数据集中查找潜在的低维子空间。

    Mar, 2018