高维嘈杂矩阵中的稀疏子矩阵检测

Sep, 2011

高维嘈杂矩阵中的稀疏子矩阵检测

Detection of a sparse submatrix of a high-dimensional noisy matrix

Cristina Butucea, Yuri I. Ingster

TL;DR提出了一种用于检测具有显著元素的子矩阵的测试方法，并计算了其检测边界和自适应敏锐度。在稀疏矩阵上得到了出色的表现，并扩展了结果以应对不同的矩阵类型和双侧替代假设。

Abstract

We observe a $N\times M$ matrix $Y_{ij}=s_{ij}+\xi_{ij}$ with $\xi_{ij}\sim {\mathcal {N}}(0,1)$ i.i.d. in $i,j$, and $s_{ij}\in \mathbb {R}$. We test the null hypothesis $s_{ij}=0$ for all $i,j$ against the alternative that there exists some submatrix of size $n\times m$ with significant elements in the sense that $s_{ij}\ge a>0$. We propose a test procedur

submatrix testing detection boundary sparse matrices minimax results adaptive testing procedure

发现论文，激发创造

极小最大子矩阵检测中的计算障碍

研究如何检测在被加性高斯噪声污染的大矩阵中具有提高平均值的小子矩阵的最小极小方法，考虑复杂度理论角度的统计性能和计算成本之间的平衡问题，得出当矩阵规模 p→无穷大时，当子矩阵大小 k =Θ(pα) 时，计算复杂度会对统计性能造成严重的惩罚，并且关于支持恢复的困难程度也得出了结果。

Sep, 2013

奇异值阈值处理下矩阵去噪的最小化风险

研究在估计一个未知的 $n*m$ 矩阵 $X_0$ 时，采用了核范数正则化的方法进行去噪，并使用软阈值法求解核范数正则化问题，同时推导了极小极大均方误差的渐进性质及其临界阈值。

Apr, 2013

高斯向量模型中稀疏性的自适应估计

该研究论文研究了高斯向量模型中的估计和测试问题，通过建立极小值分离距离和引入极小值自适应测试，实现了估计和测试，同时展示了最优算法和估计稀疏性的新方法，为各种统计模型的信号复杂度的估计提供了指导说明。

Mar, 2017

聚类、稀疏 PCA 和子矩阵定位中的信息论限制和相变

研究了检测结构化低秩信号矩阵被加性高斯噪声污染的问题，包括在高斯混合模型中的聚类，稀疏主成分分析和子矩阵定位。通过将第一和第二时刻方法应用于这些 “种植模型” 和零模型之间的似然比来导出阈值的上下界，我们证明了在信号矩阵过于微弱时没有任何算法可以检测其信号。

Jul, 2016

稀疏因子模型下噪声矩阵完成的极小值下界

该论文研究了矩阵完成问题的基本错误特征，通过分析噪声模型下的最小极大误差边界得出，结果表明最大似然估计量的复杂性正则化可以在多个噪声场景下，获得最小风险率。

Oct, 2015

高维噪声稀疏恢复的尖锐阈值

研究了在包含噪声的观测中一直稀疏模式的一致估计问题，分析了 Lasso 去恢复稀疏模式的行为，并根据高斯集合的相互不相关性条件建立了问题维数、非零元素数量和观测数之间的关系，并通过计算明确了阈值，确定了可靠恢复稀疏模式所需的观测数的下限和上限，从而解决了该问题。

May, 2006

高维极小化稀疏主子空间估计

研究高维稀疏主成分分析，提出了行稀疏和列稀疏的 lq 子空间稀疏概念，并为 0≤q≤1 证明了极小化子空间估计误差的非渐近下限和上限。这一限制完美适用于行精疏的子空间，并且近乎适用于列精疏的子空间。我们使用一种新颖的变分 sinΘ 定理进行证明，该定理可能对其他正则化谱估计问题有用。

Nov, 2012

子矩阵检测的计算下界的普适性

研究总结了在不同分布情况下计算复杂性与 KL 散度之间的统计分层次关系，揭示了计算下界中的普适性原理。

Feb, 2019

稀疏尖峰协方差矩阵的最优估计和秩检验

本文研究高维情况下的稀疏尖峰协方差矩阵模型，探讨了协方差矩阵和主子空间的极小极大估计以及极小极大排名检测。在估算尖峰协方差矩阵的最优收敛速率下建立了基于谱范数的优化，并且还建立了在谱范数下估计主子空间的最小值率，也获取了最优排名检测边界的速率。

May, 2013

稀疏带宽矩阵估计中的全有或全无统计计算相变

本文研究在一个稀疏极限下，当底层隐藏向量（构建排名为一的矩阵）非零组成部分数与向量总维数的比例为亚线性，信噪比以适当的速度趋于无穷大时，估计被加性高斯噪声矩阵污染的排名为一的矩阵的统计和计算限制，并证明了渐近互信息的显式低维变分公式，分析了稀疏状态下的近似消息传递算法。对于伯努利和伯努利 - 拉德马赫分布向量，当稀疏度和信号强度满足适当的比例关系时，我们发现渐近最小和算法均方误差的全有或全无相变。在渐近情况下，统计与算法之间的差距发散，表明近似消息传递对于稀疏恢复是非常困难的。

Jun, 2020