論文の概要: Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise

• arxiv url: http://arxiv.org/abs/2510.08541v1
• Date: Thu, 09 Oct 2025 17:53:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.28792
• Title: Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
• Title（参考訳）: 一般不均一雑音下での低ランク推定のための計算的・統計的下界
• Authors: Debsurya De, Dmitriy Kunisky,
• Abstract要約: そこで我々は,低ランク信号行列に対するスペクトルアルゴリズムの計算的最適性について検討した。 分散プロファイルがブロック構造を持つとは仮定せず、非常に一般的なプロファイルに対して同じスペクトルアルゴリズムが最適であるかもしれないことを示唆する。
• 参考スコア（独自算出の注目度）: 3.582937960220228
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent work has generalized several results concerning the well-understood spiked Wigner matrix model of a low-rank signal matrix corrupted by additive i.i.d. Gaussian noise to the inhomogeneous case, where the noise has a variance profile. In particular, for the special case where the variance profile has a block structure, a series of results identified an effective spectral algorithm for detecting and estimating the signal, identified the threshold signal strength required for that algorithm to succeed, and proved information-theoretic lower bounds that, for some special signal distributions, match the above threshold. We complement these results by studying the computational optimality of this spectral algorithm. Namely, we show that, for a much broader range of signal distributions, whenever the spectral algorithm cannot detect a low-rank signal, then neither can any low-degree polynomial algorithm. This gives the first evidence for a computational hardness conjecture of Guionnet, Ko, Krzakala, and Zdeborov\'a (2023). With similar techniques, we also prove sharp information-theoretic lower bounds for a class of signal distributions not treated by prior work. Unlike all of the above results on inhomogeneous models, our results do not assume that the variance profile has a block structure, and suggest that the same spectral algorithm might remain optimal for quite general profiles. We include a numerical study of this claim for an example of a smoothly-varying rather than piecewise-constant profile. Our proofs involve analyzing the graph sums of a matrix, which also appear in free and traffic probability, but we require new bounds on these quantities that are tighter than existing ones for non-negative matrices, which may be of independent interest.
• Abstract（参考訳）: 近年の研究では、低ランク信号行列のスパイク・ウィグナー行列モデルに関するいくつかの結果が一般化されている。 特に、分散プロファイルがブロック構造を持つ特別な場合において、一連の結果は、信号を検出して推定するための効果的なスペクトルアルゴリズムを特定し、そのアルゴリズムが成功するために必要なしきい値信号強度を特定し、いくつかの特別な信号分布において、上記のしきい値に一致する情報理論の下限を証明した。 本稿では,このスペクトルアルゴリズムの計算最適性を検討することで,これらの結果を補完する。 すなわち、より広い範囲の信号分布に対して、スペクトルアルゴリズムが低ランク信号を検出することができなければ、どちらの低次多項式アルゴリズムも検出できないことを示す。 これは、Guionnet, Ko, Krzakala, Zdeborov\'a (2023) の計算硬度予想の最初の証拠を与える。 また、同様の手法を用いて、先行処理で処理されない信号分布のクラスに対して、シャープな情報理論の下界を証明した。 不均質なモデルにおける上記の結果と異なり、我々の結果は分散プロファイルがブロック構造を持つと仮定せず、同じスペクトルアルゴリズムが極めて一般的なプロファイルに対して最適であるかもしれないことを示唆している。 この主張の数値的な研究は、一点一点のプロファイルではなく、スムーズな変化の例である。 我々の証明は、自由かつ交通確率にも現れる行列のグラフ和の分析を含むが、非負の行列に対して既存のものよりも厳密なこれらの量に対する新たな境界が必要である。

関連論文リスト

• Matrix Completion via Residual Spectral Matching [2.677354612516629]
  ノイズ行列の完成は、レコメンデーションシステム、信号処理、画像復元などへの応用により、大きな注目を集めている。 本稿では,残差の数値的および位置的情報を含む新しい残差スペクトルマッチング基準を提案する。 スパースランダム行列のスペクトル特性を解析し,低ランク摂動と部分観測の影響を限定することによって,最適統計特性を導出する。
  論文  参考訳（メタデータ） (2024-12-13T09:42:42Z)
• Matrix Denoising with Doubly Heteroscedastic Noise: Fundamental Limits and Optimal Spectral Methods [24.06775799553418]
  本研究では,列相関と列相関の両方でノイズによって劣化したランク1$の信号の特異ベクトルを推定する行列記述問題について検討する。 本研究は,2つのヘテロセダスティックノイズを重畳した行列の,情報理論的およびアルゴリズム的限界を確立する。
  論文  参考訳（メタデータ） (2024-05-22T18:38:10Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  不均一な問題に対する近似メッセージパッシングアルゴリズム(AMP)を導出する。 特に,情報理論の閾値よりも大きい信号と雑音の比を必要とする既知のアルゴリズムが,ランダムよりも優れた処理を行うための統計的・計算的ギャップの存在を同定する。
  論文  参考訳（メタデータ） (2023-02-13T19:57:17Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  我々は、$d$次元格子上の加法ガウス雑音によって破損したピースワイド定値信号について検討する。 この形式のデータは、多くのアプリケーションで自然に発生し、統計処理や信号処理の文献において、信号の検出やテスト、ノイズの除去、推定といったタスクが広く研究されている。 本稿では,未知の信号の一貫性領域によって誘導される格子の分割を推定する,分割回復の問題について考察する。 我々は、DCARTベースの手順が、下位分割を$sigma2 k*の順序で一貫して推定することを証明した。
  論文  参考訳（メタデータ） (2021-05-27T23:41:01Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  本稿では,ランダムウォークラプラシアンを用いたグラフスペクトル埋め込みが,ノード次数に対して完全に補正されたベクトル表現を生成することを示す。 次数補正ブロックモデルの特別な場合、埋め込みはK個の異なる点に集中し、コミュニティを表す。
  論文  参考訳（メタデータ） (2021-05-03T16:36:27Z)
• Learning based signal detection for MIMO systems with unknown noise statistics [84.02122699723536]
  本論文では,未知のノイズ統計による信号を堅牢に検出する一般化最大確率(ML)推定器を考案する。 実際には、システムノイズに関する統計的な知識はほとんどなく、場合によっては非ガウス的であり、衝動的であり、分析不可能である。 我々のフレームワークは、ノイズサンプルのみを必要とする教師なしの学習アプローチによって駆動される。
  論文  参考訳（メタデータ） (2021-01-21T04:48:15Z)
• All-or-nothing statistical and computational phase transitions in sparse spiked matrix estimation [35.035853993422506]
  スパース方式で近似メッセージパッシングアルゴリズムを解析する。 最小誤差と平均二乗誤差の位相遷移がすべて存在する。 スパース体制では、スパース回復が近似メッセージパッシングに困難であることを示す統計的-アルゴリズム的ギャップが分岐する。
  論文  参考訳（メタデータ） (2020-06-14T18:38:34Z)

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

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