論文の概要: What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements

• arxiv url: http://arxiv.org/abs/2510.24215v2
• Date: Mon, 03 Nov 2025 09:29:07 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-04 14:12:27.988248
• Title: What Can Be Recovered Under Sparse Adversarial Corruption? Assumption-Free Theory for Linear Measurements
• Title（参考訳）: スパース逆転破壊下で何が回収できるのか : 線形測定に対する推定自由理論
• Authors: Vishal Halder, Alexandre Reiffers-Masson, Abdeldjalil Aïssa-El-Bey, Gugan Thoppe,
• Abstract要約: 我々は$xstar$を含む最小の集合を求め、$e$を知らずに$y$から一様に回収できる。 主な結果は、$xstar + ker(U)$で、$U$は2q$行を削除して得られる$A$の可能なすべてのサブ行列の行空間の交点上の一意のプロジェクション行列であることを示している。
• 参考スコア（独自算出の注目度）: 42.543830499945926
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $A \in \mathbb{R}^{m \times n}$ be an arbitrary, known matrix and $e$ a $q$-sparse adversarial vector. Given $y = A x^\star + e$ and $q$, we seek the smallest set containing $x^\star$--hence the one conveying maximal information about $x^\star$--that is uniformly recoverable from $y$ without knowing $e$. While exact recovery of $x^\star$ via strong (and often impractical) structural assumptions on $A$ or $x^\star$ (e.g., restricted isometry, sparsity) is well studied, recoverability for arbitrary $A$ and $x^\star$ remains open. Our main result shows that the best that one can hope to recover is $x^\star + \ker(U)$, where $U$ is the unique projection matrix onto the intersection of rowspaces of all possible submatrices of $A$ obtained by deleting $2q$ rows. Moreover, we prove that every $x$ that minimizes the $\ell_0$-norm of $y - A x$ lies in $x^\star + \ker(U)$, which then gives a constructive approach to recover this set.
• Abstract（参考訳）: A \in \mathbb{R}^{m \times n}$ を任意の既知の行列とし、$e$ a $q$-スパース逆ベクトルとする。 y = A x^\star + e$ および $q$ が与えられたとき、$x^\star$ を含む最小の集合を求める。 A$ または $x^\star$ (例えば、制限等尺性、空間性) 上の強い(そしてしばしば非現実的な)構造仮定による$x^\star$ の正確な回復はよく研究されているが、任意の$A$ と $x^\star$ に対する回復性は依然として開である。 主な結果は、$x^\star + \ker(U)$であり、$U$は2q$行を削除して得られる$A$の可能なすべての部分行列の行空間の交叉上の一意の射影行列であることを示している。 さらに、$y の $\ell_0$-ノルムを最小化するすべての $x$ が $x^\star + \ker(U)$ にあることを証明する。

関連論文リスト

• The Space Complexity of Approximating Logistic Loss [11.338399194998933]
  a general $tildeOmega(dcdot mu_mathbfy(mathbfX))$ space lower bound if $epsilon$ is constant。 また、$mu_mathbfy(mathbfX)$は計算が難しいという事前予想も否定する。
  論文  参考訳（メタデータ） (2024-12-03T18:11:37Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
  任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。 我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
  論文  参考訳（メタデータ） (2024-10-07T19:47:13Z)
• Distribution-Independent Regression for Generalized Linear Models with Oblivious Corruptions [49.69852011882769]
  一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。 本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。 これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
  論文  参考訳（メタデータ） (2023-09-20T21:41:59Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  行列 $Ain mathbbRntimes d$ とテンソル $bin mathbbRn$ が与えられたとき、 $ell_infty$ の回帰問題を考える。 このような$ell_infty$レグレッションの保証を得るためには、濃密なスケッチ行列を使わなければならない。 我々はまた、OCE(Oblivious Coordinate-wise Embedding)特性を利用した $ell_infty$ guarantee regression のための新しい分析フレームワークを開発した。
  論文  参考訳（メタデータ） (2023-02-01T05:22:40Z)
• Realization of an arbitrary structure of perfect distinguishability of states in general probability theory [0.0]
  単一の要素を持つすべてのサブセットは、もちろん$mathcal A$であり、より小さなコレクションは、$Hin Mathcal A$ と $L subset H$ then $Lin mathcal A$; 言い換えれば、$mathcal A$ は $textitindependence system$ と呼ばれる、インデックスの集合上の $[n]$ である。
  論文  参考訳（メタデータ） (2023-01-16T18:33:39Z)
• Differentially Private Generalized Linear Models Revisited [30.298342283075176]
  本研究では,凸損失のある線形予測器の差分学習における$(epsilon,delta)$-differentially private Learningの問題について検討する。 特に, $tildeOleft(fracVert w*Vertsqrtn + minleftfracVert w*Vert4/3(nepsilon)2/3, fracsqrtdVert w*Vertnepsilon の過剰集団リスクの低い境界を示す。
  論文  参考訳（メタデータ） (2022-05-06T05:01:02Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。 我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
  論文  参考訳（メタデータ） (2022-02-10T16:10:41Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。 実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
  論文  参考訳（メタデータ） (2021-05-17T16:40:48Z)
• Linear Bandits on Uniformly Convex Sets [88.3673525964507]
  線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。 2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
  論文  参考訳（メタデータ） (2021-03-10T07:33:03Z)
• Optimal Mean Estimation without a Variance [103.26777953032537]
  本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。 最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
  論文  参考訳（メタデータ） (2020-11-24T22:39:21Z)
• On Computing Stable Extensions of Abstract Argumentation Frameworks [1.1251593386108185]
  textitabstract argumentation framework (sc af) は有向グラフ $(A,R)$ であり、$A$ はtextitabstract arguments の集合であり、$Rsubseteq A times A$ は textit attack relation である。 与えられた sc における全ての安定な拡張をリストアップするための、既知のバックトラックアルゴリズムの徹底的な形式的検証を示す。
  論文  参考訳（メタデータ） (2020-11-03T05:38:52Z)
• On the Regularization Effect of Stochastic Gradient Descent applied to Least Squares [0.0]
  mathbbRn times n$ の可逆 $A に対して $|Ax -b |2 rightarrow min$ に適用される勾配降下の挙動について検討する。 ここでは、$A$ に明示的な定数 $c_A$ が存在して、$$ mathbbE left| Ax_k+1-bright|2_2 leq となることを示す。
  論文  参考訳（メタデータ） (2020-07-27T03:01:09Z)
• Optimal Strategies for Graph-Structured Bandits [0.0]
  Bernoulli $!=!(nu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a in mathcalA, b in mathcalB$ with means $(mu_a,b)_a
  論文  参考訳（メタデータ） (2020-07-07T06:27:51Z)
• Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss [76.02734481158458]
  最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。 最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。 これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
  論文  参考訳（メタデータ） (2020-04-16T22:57:06Z)

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

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