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

• arxiv url: http://arxiv.org/abs/2309.09032v1
• Date: Sat, 16 Sep 2023 16:00:07 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-19 17:54:42.335398
• Title: Solving Quadratic Systems with Full-Rank Matrices Using Sparse or Generative Priors
• Title（参考訳）: スパースあるいは生成前処理を用いたフルランク行列による二次系解法
• Authors: Junren Chen, Shuai Huang, Michael K. Ng, Zhaoqiang Liu
• Abstract要約: 本稿では, 二次系$y_i=boldsymbolxtopboldsymboldsymboldA_iboldsymbolxからの信号を復元する問題に対処する。 本稿では,空間レベルの$k$を必要としないしきい値のWirtinger Flow (TWF)アルゴリズムを提案する。 スパースケースに対する我々のアプローチは、既存の証明可能なアルゴリズムのパワーファクタライゼーションよりも優れていることを示す。
• 参考スコア（独自算出の注目度）: 44.94521933974231
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 (with a good initialization) that produces a sequence linearly converging to $\boldsymbol{x}$ with $m=O(k\log n)$ measurements. Second, we explore the generative prior, assuming that $\boldsymbol{x}$ lies in the range of an $L$-Lipschitz continuous generative model with $k$-dimensional inputs in an $\ell_2$-ball of radius $r$. 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（参考訳）: 二次系 $\{y_i=\boldsymbol{x}^\top\boldsymbol{A}_i\boldsymbol{x},\i=1,\ldots,m\}$ から信号 $\boldsymbol{x} \in \mathbb{R}^n$ を回復する問題は、符号のない距離幾何学やサブ波長イメージングのような応用で頻繁に発生する。 本稿では、標準ガウス行列 $\boldsymbol{a}_i$ を用いて、$\boldsymbol{x}$ の事前知識を組み込んで $m\ll n$ という高次元の場合を扱う。 まず、$k$-sparse $\boldsymbol{x}$を検討し、空間レベル$k$を必要としないしきい値のWirtinger Flow (TWF)アルゴリズムを導入する。 twfは、$m=o(k^2\log n)$のとき、$\boldsymbol{x}$(符号フリップまで)に十分近い点を特定するスペクトル初期化と、$m=o(k\log n)$の測定値で$\boldsymbol{x}$に線形収束するシーケンスを生成するしきい値勾配降下(適切な初期化を伴う)である。 第二に、$\boldsymbol{x}$が$L$-Lipschitz連続生成モデルの範囲内であり、半径$r$の$\ell_2$-ballにおいて$k$-次元入力を持つと仮定して、生成の事前を探索する。 我々は、$O\big(\sqrt {\frac{k \log L}{m}}\big)$$\ell_2$-error given $m=O(k\log(Lnr))$ Measurementと、$m=O(k\log\frac{Lrn}{\delta^2})$のときの幾何速度で$O(\delta)$を洗練させる射影勾配降下法(PGD)アルゴリズムを開発する。 実験結果は理論的な結果と一致し、以下のことが示される。 (i)スパースケースに対する我々のアプローチは、既存の証明可能なアルゴリズムスパースパワーファクタライゼーションを著しく上回っている。 (ii) 生成前処理を利用することで、少数の二次計測値から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)

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

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