論文の概要: Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity

• arxiv url: http://arxiv.org/abs/2601.18245v1
• Date: Mon, 26 Jan 2026 08:06:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-27 15:23:08.728797
• Title: Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexity
• Title（参考訳）: 重機によるガウス位相検索と近距離サンプル複雑度による逆転破壊
• Authors: Santanu Das, Jatin Batra,
• Abstract要約: 位相探索のアルゴリズムにおける主要な考慮事項は、測定誤差に対する堅牢性である。 本稿では,重み付き雑音を用いたロバスト位相探索のための効率的なアルゴリズムについて検討する。
• 参考スコア（独自算出の注目度）: 4.655159257282136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Phase retrieval is the classical problem of recovering a signal $x^* \in \mathbb{R}^n$ from its noisy phaseless measurements $y_i = \langle a_i, x^* \rangle^2 + ζ_i$ (where $ζ_i$ denotes noise, and $a_i$ is the sensing vector) for $i \in [m]$. The problem of phase retrieval has a rich history, with a variety of applications such as optics, crystallography, heteroscedastic regression, astrophysics, etc. A major consideration in algorithms for phase retrieval is robustness against measurement errors. In recent breakthroughs in algorithmic robust statistics, efficient algorithms have been developed for several parameter estimation tasks such as mean estimation, covariance estimation, robust principal component analysis (PCA), etc. in the presence of heavy-tailed noise and adversarial corruptions. In this paper, we study efficient algorithms for robust phase retrieval with heavy-tailed noise when a constant fraction of both the measurements $y_i$ and the sensing vectors $a_i$ may be arbitrarily adversarially corrupted. For this problem, Buna and Rebeschini (AISTATS 2025) very recently gave an exponential time algorithm with sample complexity $O(n \log n)$. Their algorithm needs a robust spectral initialization, specifically, a robust estimate of the top eigenvector of a covariance matrix, which they deemed to be beyond known efficient algorithmic techniques (similar spectral initializations are a key ingredient of a large family of phase retrieval algorithms). In this work, we make a connection between robust spectral initialization and recent algorithmic advances in robust PCA, yielding the first polynomial-time algorithms for robust phase retrieval with both heavy-tailed noise and adversarial corruptions, in fact with near-linear (in $n$) sample complexity.
• Abstract（参考訳）: 位相検索は、信号$x^* \in \mathbb{R}^n$をノイズのない位相測定から回収する古典的な問題である。 位相探索の問題は、光学、結晶学、ヘテロセダスティック回帰、天体物理学などの様々な応用と共に、豊富な歴史を持っている。 位相探索のアルゴリズムにおける主要な考慮事項は、測定誤差に対する堅牢性である。 近年のアルゴリズム的ロバスト統計のブレークスルーにおいて、重み付きノイズや敵の汚職の存在下で、平均推定、共分散推定、ロバスト主成分分析(PCA)など、いくつかのパラメータ推定タスクに対して効率的なアルゴリズムが開発されている。 本稿では, 測定値$y_i$と検出ベクトル$a_i$の双方の定数が任意に逆向きに破壊される場合, 重み付き雑音を伴う頑健な位相探索のための効率的なアルゴリズムについて検討する。 この問題に対して、Buna と Rebeschini (AISTATS 2025) は、最近、サンプル複雑性$O(n \log n)$の指数時間アルゴリズムを作成した。 それらのアルゴリズムは、堅牢なスペクトル初期化、具体的には、共分散行列の上位固有ベクトルの頑健な推定を必要としており、これは既知の効率的なアルゴリズム技術を超えていると考えられている(類似スペクトル初期化は相検索アルゴリズムの大規模なファミリーの重要な要素である)。 本研究は,頑健なスペクトル初期化と近年のロバストPCAにおけるアルゴリズムの進歩とを関連付け,重み付きノイズと逆方向の汚職の両方で頑健な位相探索を行う最初の多項式時間アルゴリズムを,実際にほぼ線形($n$)のサンプル複雑性で生成する。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
  この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。 また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
  論文  参考訳（メタデータ） (2023-03-03T18:03:49Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Higher degree sum-of-squares relaxations robust against oblivious outliers [14.58610686291355]
  我々は、$Y=X*+N$という形の推定モデルを考える。 本稿では,2乗推定アルゴリズムが存在するすべての推定問題において,軽度仮定の下で信号が$X*$に回復するアルゴリズム群を紹介する。
  論文  参考訳（メタデータ） (2022-11-14T13:09:12Z)
• Towards Sample-Optimal Compressive Phase Retrieval with Sparse and Generative Priors [59.33977545294148]
  O(k log L)$サンプルは振幅に基づく経験損失関数を最小化する任意のベクトルに信号が近いことを保証するのに十分であることを示す。 この結果はスパース位相検索に適応し、基底信号が$s$-sparseおよび$n$-dimensionalである場合、$O(s log n)$サンプルは同様の保証に十分であることを示す。
  論文  参考訳（メタデータ） (2021-06-29T12:49:54Z)
• Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimation [58.24280149662003]
  本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。 我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-06-16T03:34:14Z)
• List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
  高次元におけるリストデコタブル平均推定の基本的な課題について検討する。 我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。 我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
  論文  参考訳（メタデータ） (2020-11-19T17:21:37Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)

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

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