論文の概要: The Average-Case Time Complexity of Certifying the Restricted Isometry Property

• arxiv url: http://arxiv.org/abs/2005.11270v3
• Date: Thu, 22 Apr 2021 16:00:12 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-30 09:08:35.382318
• Title: The Average-Case Time Complexity of Certifying the Restricted Isometry Property
• Title（参考訳）: 制限等長性を証明する平均ケース時間複雑性
• Authors: Yunzi Ding, Dmitriy Kunisky, Alexander S. Wein, Afonso S. Bandeira
• Abstract要約: 圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
• 参考スコア（独自算出の注目度）: 66.65353643599899
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In compressed sensing, the restricted isometry property (RIP) on $M \times N$ sensing matrices (where $M < N$) guarantees efficient reconstruction of sparse vectors. A matrix has the $(s,\delta)$-$\mathsf{RIP}$ property if behaves as a $\delta$-approximate isometry on $s$-sparse vectors. It is well known that an $M\times N$ matrix with i.i.d. $\mathcal{N}(0,1/M)$ entries is $(s,\delta)$-$\mathsf{RIP}$ with high probability as long as $s\lesssim \delta^2 M/\log N$. On the other hand, most prior works aiming to deterministically construct $(s,\delta)$-$\mathsf{RIP}$ matrices have failed when $s \gg \sqrt{M}$. An alternative way to find an RIP matrix could be to draw a random gaussian matrix and certify that it is indeed RIP. However, there is evidence that this certification task is computationally hard when $s \gg \sqrt{M}$, both in the worst case and the average case. In this paper, we investigate the exact average-case time complexity of certifying the RIP property for $M\times N$ matrices with i.i.d. $\mathcal{N}(0,1/M)$ entries, in the "possible but hard" regime $\sqrt{M} \ll s\lesssim M/\log N$. Based on analysis of the low-degree likelihood ratio, we give rigorous evidence that subexponential runtime $N^{\tilde\Omega(s^2/M)}$ is required, demonstrating a smooth tradeoff between the maximum tolerated sparsity and the required computational power. This lower bound is essentially tight, matching the runtime of an existing algorithm due to Koiran and Zouzias. Our hardness result allows $\delta$ to take any constant value in $(0,1)$, which captures the relevant regime for compressed sensing. This improves upon the existing average-case hardness result of Wang, Berthet, and Plan, which is limited to $\delta = o(1)$.
• Abstract（参考訳）: 圧縮センシングにおいて、$M \times N$ Sening matrices (ここで$M < N$)上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 行列は$(s,\delta)$-$\mathsf{rip}$プロパティを持ち、$s$-スパースベクトル上の$\delta$-approximate 等長法として振る舞う。 M\times N$ matrix with $\mathcal{N}(0,1/M)$ entry is $(s,\delta)$-$\mathsf{RIP}$ with high probability as $s\lesssim \delta^2 M/\log N$が知られている。 一方、決定論的に$(s,\delta)$-$\mathsf{RIP}$行列を構築しようとする以前のほとんどの作業は、$s \gg \sqrt{M}$で失敗した。 RIP行列を見つける別の方法は、ランダムガウス行列を描き、それが実際に RIP であることを示すことである。 しかし、s \gg \sqrt{m}$ の場合、最悪の場合と平均の場合の両方において、この認証タスクは計算的に難しいという証拠がある。 本稿では,$m\times n$行列のrip特性を i.i.d. $\mathcal{n}(0,1/m)$エントリで証明する,sqrt{m} \ll s\lesssim m/\log n$ の正確な平均ケース時間複雑性について検討する。 低度自由度比の解析に基づいて、超指数ランタイム $n^{\tilde\omega(s^2/m)}$ が要求される厳密な証拠を与え、許容される最大スパーシティと必要な計算能力とのスムーズなトレードオフを示す。 この下限は本質的に厳密であり、Koiran と Zouzias による既存のアルゴリズムのランタイムと一致する。 我々の硬さの結果、$\delta$ は任意の一定の値を $(0,1)$ で取ることができる。 これにより、wang、berthet、planの既存の平均ケースハードネス結果が改善され、これは$\delta = o(1)$に制限される。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Optimal Estimator for Linear Regression with Shuffled Labels [17.99906229036223]
  本稿では,シャッフルラベルを用いた線形回帰の課題について考察する。 mathbb Rntimes m の $mathbf Y、mathbb Rntimes p の mathbf Pi、mathbb Rptimes m$ の mathbf B、mathbb Rntimes m$ の $mathbf Win mathbb Rntimes m$ である。
  論文  参考訳（メタデータ） (2023-10-02T16:44:47Z)
• Matrix Completion in Almost-Verification Time [37.61139884826181]
  99%の行と列で$mathbfM$を完了するアルゴリズムを提供する。 本稿では,この部分完備保証を完全行列補完アルゴリズムに拡張する方法を示す。
  論文  参考訳（メタデータ） (2023-08-07T15:24:49Z)
• 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)
• Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
  我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。 我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。 我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
  論文  参考訳（メタデータ） (2022-09-30T04:15:44Z)
• 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)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
  論文  参考訳（メタデータ） (2021-09-06T14:21:43Z)
• 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)

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

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