論文の概要: Minimax optimal submatrix detection: Sharp non-asymptotic rates

• arxiv url: http://arxiv.org/abs/2605.09569v1
• Date: Sun, 10 May 2026 14:30:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-12 23:28:50.314653
• Title: Minimax optimal submatrix detection: Sharp non-asymptotic rates
• Title（参考訳）: 最小限の最適部分行列検出:シャープ非漸近速度
• Authors: Parker Knight, Julien Chhor,
• Abstract要約: 高次元ガウス行列において、サイズ$s_1倍s$の隠れ部分行列を検出する問題を考える。 我々は,最小信号強度が$*$の漸近的でない上界と下界を,I型とII型の誤差が十分小さいテストの存在を保証するのに必要かつ十分な値として提供する。 提案手法は, 独立性のある新しい試験統計を慎重に組み合わせたものである。
• 参考スコア（独自算出の注目度）: 1.7188280334580195
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of detecting a hidden submatrix of size $s_1 \times s_2$ in a high-dimensional Gaussian matrix of size $d_1 \times d_2$. Under the null hypothesis, the observed matrix has i.i.d.\ entries with distribution $N(0,1)$. Under the alternative hypothesis, there exists an unknown submatrix of size $s_1 \times s_2$ with i.i.d.\ entries with distribution $N(μ, 1)$ for some $μ>0$, while all other entries outside the submatrix are i.i.d.\ $N(0,1)$. Specifically, we provide non-asymptotic upper and lower bounds on the smallest signal strength $μ^*$ that is both necessary and sufficient to ensure the existence of a test with small enough Type I and Type II errors. We also derive novel minimax-optimal tests achieving these fundamental limits, and describe extensions of these tests that are adaptive to unknown sparsity levels $s_1$ and $s_2$. Our proposed detection procedure is a careful combination of novel test statistics which may be of independent interest. In contrast with previous work, which required restrictive assumptions on $d_1, d_2, s_1$ and $s_2$, our non-asymptotic upper and lower bounds match for any configuration of these parameters.
• Abstract（参考訳）: サイズ$s_1 \times s_2$の隠れ部分行列を、サイズ$d_1 \times d_2$の高次元ガウス行列で検出する問題を考える。 ヌル仮説の下では、観測行列は分布が$N(0,1)$の i.d.\ 個のエントリを持つ。 代替仮説の下では、分布 $N(μ, 1)$ for some $μ>0$ を持つ大きさ $s_1 \times s_2$ の未知の部分行列が存在し、サブ行列以外の全てのエントリは i.d.\ $N(0,1)$ である。 具体的には、最小信号強度$μ^*$の非漸近的上界と下界に、必要かつ十分であり、I型とII型の誤差が十分小さいテストが存在することを保証する。 また、これらの基本的な限界を達成するための新しいミニマックス最適試験を導出し、未知の空間レベル$s_1$および$s_2$に適応するこれらのテストの拡張を記述する。 提案手法は, 独立性のある新しい試験統計を慎重に組み合わせたものである。 d_1, d_2, s_1$ および $s_2$ に関する制約的な仮定を必要とする以前の研究とは対照的に、我々の非漸近的な上界と下界はこれらのパラメータの任意の構成に一致する。

関連論文リスト

• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Optimal community detection in dense bipartite graphs [0.0]
  我々は、n_1×n$の高次元二部グラフにおいて、密連結頂点のコミュニティを検出する問題を考える。 我々は,最小信号強度$delta*$の非漸近的上界および下界を,必要かつ十分であり,かつ,最小のタイプ1とタイプ2の誤差でテストが存在することを保証する。 提案試験は, 隣接行列の非線形統計値と, 独立性のある解析値を組み合わせたものである。
  論文  参考訳（メタデータ） (2025-05-23T20:58:55Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Sparse Signal Detection in Heteroscedastic Gaussian Sequence Models: Sharp Minimax Rates [1.0309387309011746]
  スパースな代替品に対する信号検出問題を、既知のスパシティ$s$に対して検討する。 ミニマックス分離半径$epsilon*$の上の上限と下限を見つけ、それらが常に一致することを証明する。 以上の結果から,epsilon*$の挙動に関する新たな位相遷移が,Sigma$の疎度レベル,$Lt$メトリック,およびヘテロスセダサシティプロファイル(herescedasticity profile)に現れる。
  論文  参考訳（メタデータ） (2022-11-15T23:53:39Z)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• Nonasymptotic one-and two-sample tests in high dimension with unknown covariance structure [0.0]
  テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。 本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
  論文  参考訳（メタデータ） (2021-09-01T06:22:53Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。