We consider the problem of localizing a submatrix with larger-than-usual
entry values inside a data matrix, without the prior knowledge of the submatrix
size. We establish an optimization framework based on a multiscale scan
statistic, and develop algorithms in order to approach the optimizer. We also
show that our estimator only requires a signal strength of the same order as
the minimax estimator with oracle knowledge of the submatrix size, to exactly
recover the anomaly with high probability. We perform some simulations that
show that our estimator has superior performance compared to other estimators
which do not require prior submatrix knowledge, while being comparatively
faster to compute.

本文研究了在不知道子矩阵大小的情况下，如何在数据矩阵中定位具有较大条目值的子矩阵。我们建立了一个基于多尺度扫描统计量的优化框架，并开发了算法来逼近优化器。我们还展示了我们的估计器只需要与最小极大估计器具有相同阶数的信号强度，就可以在高概率下准确恢复异常。我们进行了一些模拟，表明我们的估计器相对于其他不需要先前子矩阵知识的估计器具有更好的性能，同时计算速度相对更快。

自适应子矩阵定位的多尺度扫描统计量

A Multiscale Scan Statistic for Adaptive Submatrix Localization

We study the problem of detecting a structured, low-rank signal matrix
corrupted with additive Gaussian noise. This includes clustering in a Gaussian
mixture model, sparse PCA, and submatrix localization. Each of these problems
is conjectured to exhibit a sharp information-theoretic threshold, below which
the signal is too weak for any algorithm to detect. We derive upper and lower
bounds on these thresholds by applying the first and second moment methods to
the likelihood ratio between these "planted models" and null models where the
signal matrix is zero. Our bounds differ by at most a factor of root two when
the rank is large (in the clustering and submatrix localization problems, when
the number of clusters or blocks is large) or the signal matrix is very sparse.
Moreover, our upper bounds show that for each of these problems there is a
significant regime where reliable detection is information- theoretically
possible but where known algorithms such as PCA fail completely, since the
spectrum of the observed matrix is uninformative. This regime is analogous to
the conjectured 'hard but detectable' regime for community detection in sparse
graphs.

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

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

Information-theoretic bounds and phase transitions in clustering, sparse  PCA, and submatrix localization

We consider two closely related problems: planted clustering and submatrix
localization. The planted clustering problem assumes that a random graph is
generated based on some underlying clusters of the nodes; the task is to
recover these clusters given the graph. The submatrix localization problem
concerns locating hidden submatrices with elevated means inside a large
real-valued random matrix. Of particular interest is the setting where the
number of clusters/submatrices is allowed to grow unbounded with the problem
size. These formulations cover several classical models such as planted clique,
planted densest subgraph, planted partition, planted coloring, and stochastic
block model, which are widely used for studying community detection and
clustering/bi-clustering.
For both problems, we show that the space of the model parameters
(cluster/submatrix size, cluster density, and submatrix mean) can be
partitioned into four disjoint regions corresponding to decreasing statistical
and computational complexities: (1) the \emph{impossible} regime, where all
algorithms fail; (2) the \emph{hard} regime, where the computationally
expensive Maximum Likelihood Estimator (MLE) succeeds; (3) the \emph{easy}
regime, where the polynomial-time convexified MLE succeeds; (4) the
\emph{simple} regime, where a simple counting/thresholding procedure succeeds.
Moreover, we show that each of these algorithms provably fails in the previous
harder regimes.
Our theorems establish the minimax recovery limit, which are tight up to
constants and hold with a growing number of clusters/submatrices, and provide a
stronger performance guarantee than previously known for polynomial-time
algorithms. Our study demonstrates the tradeoffs between statistical and
computational considerations, and suggests that the minimax recovery limit may
not be achievable by polynomial-time algorithms.

研究插入聚类和子矩阵定位问题，提出四个算法，每个算法都在困难度更大的情况下无法成功。研究表明，机器学习和统计推断等算法之间的权衡，以及极小化恢复限制可能无法通过多项式时间算法实现。