論文の概要: Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis

• arxiv url: http://arxiv.org/abs/1912.13091v1
• Date: Mon, 30 Dec 2019 21:31:15 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-17 01:57:39.965200
• Title: Basis Pursuit and Orthogonal Matching Pursuit for Subspace-preserving Recovery: Theoretical Analysis
• Title（参考訳）: 部分空間保存回復のための基底法と直交整合法:理論的解析
• Authors: Daniel P. Robinson and Rene Vidal and Chong You
• Abstract要約: 部分空間保存の回復を保証する様々な幾何学的条件を示す。 提案した条件のいくつかはスパース信号回復文学におけるよく知られた条件の一般化であることを示す。
• 参考スコア（独自算出の注目度）: 27.043917504997516
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Given an overcomplete dictionary $A$ and a signal $b = Ac^*$ for some sparse vector $c^*$ whose nonzero entries correspond to linearly independent columns of $A$, classical sparse signal recovery theory considers the problem of whether $c^*$ can be recovered as the unique sparsest solution to $b = A c$. It is now well-understood that such recovery is possible by practical algorithms when the dictionary $A$ is incoherent or restricted isometric. In this paper, we consider the more general case where $b$ lies in a subspace $\mathcal{S}_0$ spanned by a subset of linearly dependent columns of $A$, and the remaining columns are outside of the subspace. In this case, the sparsest representation may not be unique, and the dictionary may not be incoherent or restricted isometric. The goal is to have the representation $c$ correctly identify the subspace, i.e. the nonzero entries of $c$ should correspond to columns of $A$ that are in the subspace $\mathcal{S}_0$. Such a representation $c$ is called subspace-preserving, a key concept that has found important applications for learning low-dimensional structures in high-dimensional data. We present various geometric conditions that guarantee subspace-preserving recovery. Among them, the major results are characterized by the covering radius and the angular distance, which capture the distribution of points in the subspace and the similarity between points in the subspace and points outside the subspace, respectively. Importantly, these conditions do not require the dictionary to be incoherent or restricted isometric. By establishing that the subspace-preserving recovery problem and the classical sparse signal recovery problem are equivalent under common assumptions on the latter, we show that several of our proposed conditions are generalizations of some well-known conditions in the sparse signal recovery literature.
• Abstract（参考訳）: あるスパースベクトル $c^*$ に対して、超完全辞書 $a$ と信号 $b = ac^*$ が与えられ、その非ゼロエントリが$a$ の線形独立列に対応すると、古典的なスパース信号回復理論は、$c^*$ が、$b = a c$ に対する一意なスパース解として回収できるかどうかという問題を考察する。 辞書 $a$ が非一貫性または制限された等尺性である場合、実用的なアルゴリズムによってそのような回復が可能であることはよく理解されている。 本稿では、$b$ が部分空間 $\mathcal{S}_0$ に含まれるようなより一般的な場合を考える。 この場合、最も広い表現は一意ではないかもしれないし、辞書は不整合あるいは制限された等尺的でないかもしれない。 目的は、$c$の表現を正しくサブ空間を識別させることであり、すなわち$c$の 0 でないエントリは、サブ空間 $\mathcal{S}_0$ にある$A$の列に対応するべきである。 このような表現 $c$ は部分空間保存(subspace-serving)と呼ばれ、これは高次元データにおいて低次元構造を学習するための重要な応用を見出した鍵概念である。 部分空間保存回復を保証する様々な幾何学的条件を示す。 それらのうち, 主結果は, 部分空間内の点の分布と, 部分空間の点と部分空間の外側の点との類似性をそれぞれ捉える被覆半径と角距離によって特徴づけられる。 重要なことに、これらの条件は辞書が不整合あるいは制限された等尺性である必要はない。 部分空間保存回復問題と古典的スパース信号回復問題は,後者の一般的な仮定で等価であることを示すことにより,提案した条件のいくつかはスパース信号回復の文献でよく知られた条件の一般化であることを示す。

関連論文リスト

• Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity [3.9657575162895196]
  曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。 最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
  論文  参考訳（メタデータ） (2024-11-13T16:58:51Z)
• 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)
• Holograms In Our World [0.0]
  AdS/CFT において、絡み合いウェッジ EW$(B)$ は境界領域 $B$ から再構成できるバルク幾何学の部分である。 我々は、max-とmin-entanglement wedge、$e_rm max(a)$と$e_rm min(a)$を定義する。
  論文  参考訳（メタデータ） (2023-02-15T19:00:01Z)
• Asymptotic Tensor Powers of Banach Spaces [77.34726150561087]
  ユークリッド空間は、そのテンソル半径がその次元と等しい性質によって特徴づけられることを示す。 また、領域または範囲がユークリッドである作用素のテンソル半径がその核ノルムと等しいことを示す。
  論文  参考訳（メタデータ） (2021-10-25T11:51:12Z)
• 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)
• Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
  我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。 規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
  論文  参考訳（メタデータ） (2021-05-31T16:10:49Z)
• 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)
• Optimal Approximation Rates and Metric Entropy of ReLU$^k$ and Cosine Networks [0.0]
  対応する浅層ニューラルネットワークによって効率的に近似できる関数の最大のバナッハ空間は、集合 $pmsigma(omegacdot x + b)$ の閉凸包のゲージによってノルムが与えられる空間であることを示す。 これらのゲージ空間の単位球の$L2$-metricエントロピーの精度を確立し、その結果、浅いReLU$k$ネットワークに対する最適近似速度を導出する。
  論文  参考訳（メタデータ） (2021-01-29T02:29:48Z)
• Stochastic Linear Bandits with Protected Subspace [51.43660657268171]
  線形目的関数を最適化するが、報酬は未知の部分空間にのみ得られる線形帯域問題の変種について検討する。 特に、各ラウンドでは、学習者は、目的または保護されたサブスペースを、アクションの選択とともにクエリするかどうかを選択する必要がある。 提案アルゴリズムはOFULの原理から導かれるもので,保護された空間を推定するためにクエリのいくつかを利用する。
  論文  参考訳（メタデータ） (2020-11-02T14:59:39Z)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)

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

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