論文の概要: Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors

• arxiv url: http://arxiv.org/abs/2309.09032v2
• Date: Tue, 29 Oct 2024 18:39:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-10-31 14:23:45.749582
• Title: Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors
• Title（参考訳）: スパース・ジェネレーティブ・プライオリティを用いたフルランク行列による二次系の解法
• Authors: Junren Chen, Michael K. Ng, Zhaoqiang Liu,
• Abstract要約: 二次系$y_i=boldsymbol xtopboldsymbol A_iboldsymbol x, i=1,ldots,m$とフルランク行列$boldsymbol A_i$からの信号を回復する問題は、未割り当て距離幾何学やサブ波長イメージングなどの応用で頻繁に発生する。 本稿では、$mll n$ が $boldsymbol x$ の事前知識を取り入れた高次元の場合について述べる。
• 参考スコア（独自算出の注目度）: 33.0212223058894
• License:
• Abstract: The problem of recovering a signal $\boldsymbol x\in \mathbb{R}^n$ from a quadratic system $\{y_i=\boldsymbol x^\top\boldsymbol A_i\boldsymbol x,\ i=1,\ldots,m\}$ with full-rank matrices $\boldsymbol A_i$ frequently arises in applications such as unassigned distance geometry and sub-wavelength imaging. With i.i.d. standard Gaussian matrices $\boldsymbol A_i$, this paper addresses the high-dimensional case where $m\ll n$ by incorporating prior knowledge of $\boldsymbol x$. First, we consider a $k$-sparse $\boldsymbol x$ and introduce the thresholded Wirtinger flow (TWF) algorithm that does not require the sparsity level $k$. TWF comprises two steps: the spectral initialization that identifies a point sufficiently close to $\boldsymbol x$ (up to a sign flip) when $m=O(k^2\log n)$, and the thresholded gradient descent which, when provided a good initialization, produces a sequence linearly converging to $\boldsymbol x$ with $m=O(k\log n)$ measurements. Second, we explore the generative prior, assuming that $x$ lies in the range of an $L$-Lipschitz continuous generative model with $k$-dimensional inputs in an $\ell_2$-ball of radius $r$. With an estimate correlated with the signal, we develop the projected gradient descent (PGD) algorithm that also comprises two steps: the projected power method that provides an initial vector with $O\big(\sqrt{\frac{k \log L}{m}}\big)$ $\ell_2$-error given $m=O(k\log(Lnr))$ measurements, and the projected gradient descent that refines the $\ell_2$-error to $O(\delta)$ at a geometric rate when $m=O(k\log\frac{Lrn}{\delta^2})$. Experimental results corroborate our theoretical findings and show that: (i) our approach for the sparse case notably outperforms the existing provable algorithm sparse power factorization; (ii) leveraging the generative prior allows for precise image recovery in the MNIST dataset from a small number of quadratic measurements.
• Abstract（参考訳）: 信号 $\boldsymbol x\in \mathbb{R}^n$ を二次系 $\{y_i=\boldsymbol x^\top\boldsymbol A_i\boldsymbol x,\i=1,\ldots,m\}$ から回復する問題は、符号なし距離幾何学やサブ波長イメージングなどの応用において頻繁に発生する。 i.d.d.標準ガウス行列 $\boldsymbol A_i$ では、$m\ll n$ が $\boldsymbol x$ の事前知識を取り入れた高次元ケースに対処する。 まず、$k$-sparse $\boldsymbol x$を検討し、空間レベル$k$を必要としないしきい値のWirtinger Flow (TWF)アルゴリズムを導入する。 TWFは、$m=O(k^2\log n)$に十分近い点を特定するスペクトル初期化と、$m=O(k^2\log n)$に良い初期化を与えると、$m=O(k\log n)$で$\boldsymbol x$に線形収束する列を生成する閾値勾配勾配の2つのステップからなる。 第二に、$x$が$L$-Lipschitz連続生成モデルの範囲内にあり、$k$-次元入力が$\ell_2$-ball of radius $r$であるとする。 信号と相関した推定値を用いて、$O\big(\sqrt {\frac{k \log L}{m}}\big)$$\ell_2$-error given $m=O(k\log(Lnr))$の測定値と$O(\delta)$を$m=O(k\log\frac{Lrn}{\delta^2})$のときの幾何的な速度で、$O(\delta)$を洗練させる射影勾配降下(PGD)アルゴリズムを開発する。 実験結果は、我々の理論的知見を裏付けるものであり、次のように示している。 (i)スパースケースに対する我々のアプローチは、特に既存の証明可能なアルゴリズムスパースパワーファクターよりも優れている。 (II) 生成前の手法を利用することで、少数の2次測定値からMNISTデータセットの正確な画像復元が可能となる。

関連論文リスト

• 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)
• Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
  我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。 特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。 主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
  論文  参考訳（メタデータ） (2023-12-14T12:53:34Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。 本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。 また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
  論文  参考訳（メタデータ） (2023-09-25T17:54:19Z)
• 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)
• Misspecified Phase Retrieval with Generative Priors [15.134280834597865]
  単一のインデックスモデル $y の $m$ i.d.realization から$n$-dimensional signal $mathbfx$ を推定する。 どちらのステップも、適切な条件下では、$sqrt(klog L)cdot (log m)/m$の統計的レートを享受できることが示される。
  論文  参考訳（メタデータ） (2022-10-11T16:04:11Z)
• High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representation [89.21686761957383]
  2層ネットワークにおける第1層パラメータ $boldsymbolW$ の勾配降下ステップについて検討した。 我々の結果は、一つのステップでもランダムな特徴に対してかなりの優位性が得られることを示した。
  論文  参考訳（メタデータ） (2022-05-03T12:09:59Z)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Optimal Combination of Linear and Spectral Estimators for Generalized Linear Models [59.015960528781115]
  最適に $hatboldsymbol xrm L$ と $hatboldsymbol xrm s$ を組み合わせる方法を示す。 我々は,$(boldsymbol x, hatboldsymbol xrm L, hatboldsymbol xrm s)$の制限分布を確立するために,Adroximate Message Passing (AMP)アルゴリズムの設計と解析を行う。
  論文  参考訳（メタデータ） (2020-08-07T18:20:05Z)
• Tree-Projected Gradient Descent for Estimating Gradient-Sparse Parameters on Graphs [10.846572437131872]
  mathbbRp$における勾配スパースパラメータの$boldsymboltheta*の推定について検討した。 損失に対する厳密な凸性および滑らかさの仮定が適切に制限されている場合、この推定器は、$G$とは独立な乗法定数までの2乗誤差リスク $fracs*n log (1+fracps*)$を達成する。
  論文  参考訳（メタデータ） (2020-05-31T20:08:13Z)

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

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