Mar, 2015

字典学习中 ITKM 算法的收敛半径和样本复杂度

PDF
TL;DR本文通过迭代阈值和 K-means 算法展示了，只要初始化在收敛半径内，即在动态范围的倒数 $\log K$ 因子内，样本量与 $K\log K\tilde \varepsilon^{-2}$ 成比例，就可以从带噪声的 $S$ 稀疏信号中恢复出具有 $K$ 个原子的生成字典，误差为 $\tilde \varepsilon$。针对信号维 $\mathrm {d}$ 的平方根级别的稀疏度和目标误差 $K^{-\ell}$ 的情况，$S$ 随着 $S \leq \mathrm {d}/(\ell \log K)$ 尺度而缩小，对于任意目标误差结果是有效的。
iterative thresholdingk-meansgenerating dictionarysparse signalssample size
发现论文，激发创造
  • 局部识别过完备字典

    本文提出了一种新的最大化准则，其可概括 K-means 准则，用于稳定识别过完备的互相关联的词典并从具有稀疏水平的训练信号中提供精确恢复，同时提供了一个简单的迭代阈值及 K-means 算法（ITKM）来实际寻找这一准则的局部极大值，证明了其在多次实验中的局部高效性。

    Jan, 2014

  • 广义核稀疏化

    本文提出了四种改进方法，包括将 Kernel Thinning 直接应用于目标 Reproducing Kernel Hilbert Space 以获得更紧密的无维度保证，使用分数功率核对于不平滑的核可以获得优于蒙特卡罗的保证，并且将 KT 应用于目标和功率核的总和可以同时继承两种方法的保证，在多维度和压缩挑战性微分方程后验的情况下，可以显着减少集成误差。

    Oct, 2021

  • 稀疏字典学习的素描算法：PTAS 和转轴流式处理

    通过新技术扩展基于草图的方法，开展了稀疏字典学习和欧氏 k-means 聚类问题的研究，在快速算法方面获得了对 $k$-means 聚类问题的新方法，并推广到稀疏字典学习问题。在流算法方面，得到了字典学习和 $k$-means 聚类的新上界和下界。

    Oct, 2023

  • 字典学习的样本复杂度

    本文从统计学习理论的角度探讨了信号处理中字典学习的一些问题，包括在一定约束条件下的系数选择和新信号表示误差的广义界限等，并提供了一些定理和结果。

    Nov, 2010

  • 受限等距常数的新界

    本文研究了压缩感知中的 $\ell_1$ 最小化问题，证明了只要压缩感知矩阵的限制等距常数 $\delta_k$ 满足 $\delta_k < 0.307$，在无噪声情况下可以完美地恢复 $k$- 稀疏信号，并且可以在有噪声情况下稳定地估计 $k$- 稀疏信号。

    Nov, 2009

  • 去偏分布压缩

    现代压缩方法可以比独立同分布采样更简洁地概括目标分布 P，但需要访问低偏差输入序列，例如迅速收敛到 P 的马尔可夫链。我们介绍了一套适用于带偏差输入序列压缩的新型压缩方法。在给定 n 个针对错误分布的点和二次时间的情况下，Stein Kernel Thinning (SKT) 返回具有对 P 的最大平均误差 (MMD) 为 O (n^{-1/2}) 的√n 个等权重点。对于更大规模的压缩任务，Low-rank SKT 使用自适应的低秩去偏过程以次二次时间实现相同的效果，该过程可能是独立感兴趣的。对于支持单纯或保持常量权重的下游任务，Stein Recombination 和 Stein Cholesky 具有更大的简洁性，可以与最少的 poly-log (n) 个加权点的 SKT 保证相匹配。这些进展的基础是关于单纯加权负样本集的新保证，核矩阵的谱衰减和 Stein 核希尔伯特空间的覆盖数。在我们的实验中，我们的技术提供了简洁准确的后验总结，同时克服了因预烧、近似马尔可夫链蒙特卡罗和淬火而产生的偏差。

    Apr, 2024

  • 交替极小化算法在字典学习中的收敛性

    本文研究了字典学习中两种流行的交替最小化算法的收敛性，在给定合适初始化条件的情况下，这两种算法都可以收敛到生成字典，适用于稀疏系数的数据模型，更好地拟合真实数据

    Apr, 2023

  • 稀疏字典学习在噪声存在下的局部稳定性和鲁棒性

    本文采用概率模型研究了稀疏编码的本地最小值问题，在考虑超完备字典和有噪信号的情况下，证明了稀疏编码接近参考字典生成的信号的局部最小值，同时分析了噪声、信号维度、原子数量、稀疏度和观察数量等关键量如何随之缩放。

    Oct, 2012

  • 压缩感知的迭代硬阈值

    本文探讨压缩感知技术中的迭代硬阈值算法的理论分析，证明该算法具有近乎最优的误差保证、鲁棒性、最小的观察数、可用于任何可计算其算符和伴随算符的采样算子、线性问题大小的内存要求、迭代计算复杂度与测量算子或其伴随算子的应用次序相同、仅取决于信号信噪比的形式的对数的一种形式的迭代次数、性能保证仅取决于采样算子和信号稀疏性的特性。

    May, 2008

  • 关于字典学习中 L^1 收缩算法本地正确性的研究

    该论文探讨了字典学习问题的局部解决方案，基于随机稀疏模型，通过低秩矩阵补全问题的工具，克服了一些技术上的难点，并建立了当样本数满足某些条件时，字典和系数的组合可以成为 L1 范数的局部最优解这一结果。

    Jan, 2011