論文の概要: A General Algorithm for Solving Rank-one Matrix Sensing

• arxiv url: http://arxiv.org/abs/2303.12298v1
• Date: Wed, 22 Mar 2023 04:07:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-23 15:18:13.631832
• Title: A General Algorithm for Solving Rank-one Matrix Sensing
• Title（参考訳）: ランク1行列センシングの一般解法
• Authors: Lianke Qin, Zhao Song, Ruizhe Zhang
• Abstract要約: マトリックスセンシングの目標は、一連の測定に基づいて、mathbbRn×n$の行列$A_starを復元することである。 本稿では、このランク-$kの仮定を緩和し、より一般的な行列センシング問題を解く。
• 参考スコア（独自算出の注目度）: 15.543065204102714
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Matrix sensing has many real-world applications in science and engineering, such as system control, distance embedding, and computer vision. The goal of matrix sensing is to recover a matrix $A_\star \in \mathbb{R}^{n \times n}$, based on a sequence of measurements $(u_i,b_i) \in \mathbb{R}^{n} \times \mathbb{R}$ such that $u_i^\top A_\star u_i = b_i$. Previous work [ZJD15] focused on the scenario where matrix $A_{\star}$ has a small rank, e.g. rank-$k$. Their analysis heavily relies on the RIP assumption, making it unclear how to generalize to high-rank matrices. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem. Given an accuracy parameter $\delta \in (0,1)$, we can compute $A \in \mathbb{R}^{n \times n}$ in $\widetilde{O}(m^{3/2} n^2 \delta^{-1} )$, such that $ |u_i^\top A u_i - b_i| \leq \delta$ for all $i \in [m]$. We design an efficient algorithm with provable convergence guarantees using stochastic gradient descent for this problem.
• Abstract（参考訳）: マトリックスセンシングは、システム制御、距離埋め込み、コンピュータビジョンなど、科学や工学において多くの実世界の応用がある。 行列センシングの目標は、行列 $A_\star \in \mathbb{R}^{n \times n}$ を $(u_i,b_i) \in \mathbb{R}^{n} \times \mathbb{R}$ の列に基づいて、$u_i^\top A_\star u_i = b_i$ とする。 以前の作業 [ZJD15] では、行列 $A_{\star}$ が小さなランク、例えば rank-$k$ を持つシナリオに焦点を当てていた。 それらの解析はRIP仮定に大きく依存しており、高階行列への一般化方法が不明である。 本稿では,このランク$k$仮定を緩和し,より一般的な行列センシング問題を解く。 精度パラメータが $\delta \in (0,1)$ であれば、$A \in \mathbb{R}^{n \times n}$ in $\widetilde{O}(m^{3/2} n^2 \delta^{-1} )$ を計算でき、$ |u_i^\top A u_i - b_i| \leq \delta$ for all $i \in [m]$ である。 この問題に対して確率勾配勾配を用いた証明可能な収束保証付き効率的なアルゴリズムを設計する。

関連論文リスト

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。 アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
  論文  参考訳（メタデータ） (2024-10-26T06:21:42Z)
• 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)
• Structured Semidefinite Programming for Recovering Structured Preconditioners [41.28701750733703]
  正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。 我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
  論文  参考訳（メタデータ） (2023-10-27T16:54:29Z)
• Solving Attention Kernel Regression Problem via Pre-conditioner [9.131385887605935]
  我々は2種類の回帰問題に対するアルゴリズムを設計する:$min_xin mathbbRd|(Atop A)jx-b|$ for any positive integer $j$。 2番目のプロキシは、$exp(AAtop)$で表され、回帰$min_xin mathbbRn|exp(AAtop)xb |$で表されるグラム行列に指数的にエントリワイドを適用する。
  論文  参考訳（メタデータ） (2023-08-28T04:37:38Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension [18.57735939471469]
  我々は注意問題のスパシフィケーションを考慮する。 超大規模特徴量の場合、文の長さをほぼ線形に縮めることができる。
  論文  参考訳（メタデータ） (2023-04-10T05:52:38Z)
• 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)
• 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)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。 Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
  論文  参考訳（メタデータ） (2020-05-22T16:55:01Z)

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

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