論文の概要: The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
- arxiv url: http://arxiv.org/abs/2509.01809v1
- Date: Mon, 01 Sep 2025 22:26:37 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-04 15:17:03.852082
- Title: The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
- Title（参考訳）: スパース率の値:スパース測定とスパース測定によるスパース回収に有効な条件
- Authors: Youssef Chaabouni, David Gamarnik,
- Abstract要約: 雑音予測を用いてスパース信号の支持を回復する問題を考察する。
我々はスパース測定行列を用いてスパース回収に成功したサンプルサイズについて十分な条件を定めている。
- 参考スコア（独自算出の注目度）: 1.2604738912025477
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider the problem of recovering the support of a sparse signal using noisy projections. While extensive work has been done on the dense measurement matrix setting, the sparse setting remains less explored. In this work, we establish sufficient conditions on the sample size for successful sparse recovery using sparse measurement matrices. Bringing together our result with previously known necessary conditions, we discover that, in the regime where $ds/p \rightarrow +\infty$, sparse recovery in the sparse setting exhibits a phase transition at an information-theoretic threshold of $n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$, where $p$ denotes the signal dimension, $s$ the number of non-zero components of the signal, and $d$ the expected number of non-zero components per row of measurement. This expression makes the price of sparsity explicit: restricting each measurement to $d$ non-zeros inflates the required sample size by a factor of $\log{s}/\log\left(ds/p\right)$, revealing a precise trade-off between sampling complexity and measurement sparsity. Additionally, we examine the effect of sparsifying an originally dense measurement matrix on sparse signal recovery. We prove in the regime of $s = \alpha p$ and $d = \psi p$ with $\alpha, \psi \in \left(0,1\right)$ and $\psi$ small that a sample of size $n^{\text{Sp-ified}}_{\text{INF}} = \Theta\left(p / \psi^2\right)$ is sufficient for recovery, subject to a certain uniform integrability conjecture, the proof of which is work in progress.
- Abstract（参考訳）: 雑音予測を用いてスパース信号の支持を回復する問題を考察する。
密度測定マトリクス設定について広範な研究がなされているが、スパース設定はいまだに調査されていない。
本研究では,スパース測定行列を用いたスパース回収を成功させるために,サンプルサイズに関する十分な条件を確立する。
ds/p \rightarrow +\infty$, スパース・セッティングにおけるスパース・リカバリが、情報理論上のしきい値である$n_{\text{INF}}^{\text{SP}} = \Theta\left(s\log\left(p/s\right)/\log\left(ds/p\right)\right)$, $p$ は信号次元を表し、$s$ は信号の非ゼロ成分の数を表し、$d$ は測定の行当たりの非ゼロ成分の数である。
それぞれの測定値を$d$non-zerosに制限すると、必要なサンプルサイズを$\log{s}/\log\left(ds/p\right)$で膨らませる。
さらに,元の密度測定行列のスペース化がスパース信号の回復に及ぼす影響について検討した。
我々は $s = \alpha p$ と $d = \psi p$ with $\alpha, \psi \in \left(0,1\right)$ と $\psi$ small の体制で、サイズ $n^{\text{Sp-ified}}_{\text{INF}} = \Theta\left(p / \psi^2\right)$ のサンプルが、ある一様可積分性予想の下で回復するのに十分であることを示す。
関連論文リスト
- Spike-and-Slab Posterior Sampling in High Dimensions [11.458504242206862]
スパイク・アンド・スラブ先行法[MB88]による後方サンプリングは,ベイズ・スパース線形回帰の理論的金標準法であると考えられる。
我々は,任意のSNRに適用可能なスパイク・アンド・スラブ後続サンプリングのための最初の証明可能なアルゴリズムを提示し,問題次元における測定カウントサブを使用する。
ラプラス拡散密度を用いたスパイク・アンド・スラブ後方サンプリングに拡張し、$sigma = O(frac1k)$が有界である場合にも同様の保証を達成する。
論文 参考訳（メタデータ） (2025-03-04T17:16:07Z) - Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
単一インデックス対象関数 $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ の勾配勾配勾配学習問題について検討する。
SGDに基づくアルゴリズムにより最適化された2層ニューラルネットワークは、情報指数に支配されない複雑さで$f_*$を学習する。
論文 参考訳（メタデータ） (2024-06-03T17:56:58Z) - Robust 1-bit Compressed Sensing with Iterative Hard Thresholding [18.05573480691047]
1ビット圧縮センシングでは、$k$スパース単位ベクトル$xin Sn-1$を$epsilon$エラー内で推定する。
本稿では,一部の計測値のフリップが可能な雑音バージョンを,潜在的に敵によって検討する。
BIHTallyは$tildeO(epsilon+tau)$エラーで$x$と見積もる。
論文 参考訳（メタデータ） (2023-10-12T03:41:32Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳（メタデータ） (2023-04-05T07:24:19Z) - Sparse Recovery with Shuffled Labels: Statistical Limits and Practical
Estimators [23.313461266708877]
置換行列 $bPitrue$ とスパース信号 $bbetatrue$ をシャッフルラベルから再構成する。
提案した推定器は, 穏やかな条件下で, 基本トラス$(bPitrue, supp(bbetatrue))$が得られることを示す。
論文 参考訳（メタデータ） (2023-03-20T16:14:58Z) - 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) - Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。
我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
論文 参考訳（メタデータ） (2022-03-18T18:50:52Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z) - Just Least Squares: Binary Compressive Sampling with Low Generative
Intrinsic Dimension [12.67951378791069]
雑音や符号フリップによって劣化した$m$のバイナリ測定から$n$の次元信号を復元することを検討する。
二乗測定モデルは非常に非線形であるが、最小二乗復号器を提案する。
論文 参考訳（メタデータ） (2021-11-29T12:06:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。