MMJul, 2016

改进的随机迹估计方法：基于互不偏的基底

PDF
TL;DR使用互不偏基的基向量作为寻味向量，以估计矩阵迹，要求生成每个向量仅需 O (log (n)) 个随机比特，从而显著地提高了单次采样方差，同时也改进了传统方法。
发现论文，激发创造
  • 隐式矩阵迹估计器样本大小的改进界限

    本文研究了通过矩阵 - 向量乘法计算跟踪矩阵 A 的隐式给定的蒙特卡洛方法，通过随机向量的平均值估计跟踪值的相对误差，并证明了 Hutchinson，Gaussian 和单位矢量（有和无替换）概率分布所需要的实现数量 N。结果表明，该方法能够在不同的矩阵情况下提供更有效或相对无效的随机估计方法。

    Aug, 2013

  • Hutch++：最优随机迹估计

    研究矩阵的迹估计问题，提出一种通过矩阵向量乘法计算正半定矩阵的迹的新的随机算法 Hutch ++，其利用低秩近似步骤降低估计值的方差，证明其复杂度在所有矩阵向量查询算法中是最优的。

    Oct, 2020

  • 关于不定矩阵的随机迹估计及其在行列式中的应用

    本文提出了一种针对不定矩阵的轨迹估计技术，使用拉德马赫或高斯随机向量的新尾部界限显著提高了现有结果，同时针对 Lanczos 方法的轨迹估计也做了改进和扩展。

    May, 2020

  • 利用稀疏采样的自由随机矩阵进行支持恢复

    本文研究了具有 Beroulli-Gaussian 噪声的稀疏向量通过随机矩阵的压缩采样模型，考虑了多种信息论性能指标和估计方法。

    Aug, 2012

  • 多元迹估计：基于量子态空间线性代数

    本文提出了一种适用于近似多元痕迹（即矩阵乘积的痕迹）的量子算法，该算法通过一系列低层电路构造操作将多元痕迹公式直接转化为量子电路，并利用 qMSLA 操作构建状态准备电路，输出两个编码多变痕迹的状态准备电路。此算法仅使用状态准备电路作为输入，不依赖于诸如 Block Encodings 之类较难合成的构造，同时也不依赖于特定硬件（如 QRAM），突显其通用性和实用性。

    May, 2024

  • 迹的最优草图估计

    本文研究了矩阵迹估计的算法，提出了 Hutch++ 以及一种新的非自适应算法，通过实验证明了该算法的优越性。

    Nov, 2021

  • 古典矩阵群上的线性函数

    研究使用 Haar measure 进行随机矩阵采样后，其迹与标准正态分布之间的总变差距离上界，并将 Stein 方法的交换对扩展到存在连续对称性的情况，取得了类似结果的成果.

    Sep, 2005

  • 从截断样本中高效地估计高维统计量

    该研究提出了一种高效的算法，利用截断样本可以无限精确地估计多元正态分布的参数，前提是拥有样本集的访问权，并且该样本集存在具有非微不足道的测度。

    Sep, 2018

  • 随机线性估计中的互信息：超越 i.i.d. 矩阵

    本文通过自适应插值方法和随机矩阵理论证明了 Takeda，Uda，Kabashima 和 Tulino，Verdu，Caire 和 Shamai 使用复制方法提出的公式适用于一类具有旋转不变性质的矩阵，进而超越了原有广泛应用于压缩感知和统计学的噪声线性估计问题中的 i.i.d. 矩阵假设。

    Feb, 2018

  • 带随机线性测量的无标记感知

    本文研究了线性感知系统在无标签观测的情况下如何解决问题，着重于利用具有独立同分布条目的随机矩阵来解决。我们证明了如果感知矩阵 A 具有超采样率为 2 或更高，则可以在不知道 y 中观察顺序的情况下达到准确恢复 x 的目标，而且对于任何 2K 个 y 观测到的条目都足以恢复 x。 这个结果意味着具有超采样因子 2 的确定性未标记感知矩阵可以实现完美重建。

    Dec, 2015