論文の概要: 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) - Distribution-Independent Regression for Generalized Linear Models with
Oblivious Corruptions [49.69852011882769]
一般化線形モデル (GLMs) の重畳雑音の存在下での回帰問題に対する最初のアルゴリズムを示す。
本稿では,この問題に最も一般的な分布非依存設定で対処するアルゴリズムを提案する。
これは、サンプルの半分以上を任意に破損させる難聴ノイズを持つGLMレグレッションに対する最初の新しいアルゴリズムによる結果である。
論文 参考訳（メタデータ） (2023-09-20T21:41:59Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。