論文の概要: Non-Convex Compressed Sensing with Training Data
- arxiv url: http://arxiv.org/abs/2101.08310v1
- Date: Wed, 20 Jan 2021 20:30:59 GMT
- ステータス: 処理完了
- システム内更新日: 2021-03-22 01:14:20.076116
- Title: Non-Convex Compressed Sensing with Training Data
- Title（参考訳）: トレーニングデータを用いた非凸圧縮センシング
- Authors: G. Welper
- Abstract要約: 我々は、行列$A$上の比較的少数の仮定を持つ1層の線形ニューラルネットワークの範囲において高い確率で元の問題$Ax = b$の解決策を見つける。
本稿では、適切な初期値の代わりに、圧縮センシング問題に関連する追加のトレーニング問題 $Ax = B_l$, $l=1, dots, p$ が提供される代替案を検討する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Efficient algorithms for the sparse solution of under-determined linear
systems $Ax = b$ are known for matrices $A$ satisfying suitable assumptions
like the restricted isometry property (RIP). Without such assumptions little is
known and without any assumptions on $A$ the problem is $NP$-hard. A common
approach is to replace $\ell_1$ by $\ell_p$ minimization for $0 < p < 1$, which
is no longer convex and typically requires some form of local initial values
for provably convergent algorithms.
In this paper, we consider an alternative, where instead of suitable initial
values we are provided with extra training problems $Ax = B_l$, $l=1, \dots, p$
that are related to our compressed sensing problem. They allow us to find the
solution of the original problem $Ax = b$ with high probability in the range of
a one layer linear neural network with comparatively few assumptions on the
matrix $A$.
- Abstract（参考訳）: 未決定線型系のスパース解に対する効率的なアルゴリズムは、制限等尺性(RIP)のような適切な仮定を満たす行列に対して$Ax = b$ が知られている。
そのような仮定がなければほとんど知られておらず、$A$の仮定がなければ、問題は$NP$-hardである。
一般的なアプローチは、$\ell_1$を$\ell_p$ minimizationを$0 < p < 1$に置き換えることである。
そこで本研究では,初期値に代えて,圧縮センシング問題に関連する追加のトレーニング問題として$Ax = B_l$, $l=1, \dots, p$が提供される。
これにより、元の問題である$Ax = b$の解を1層線形ニューラルネットワークの範囲内で高い確率で見つけることができ、行列$A$に対する仮定は比較的少ない。
関連論文リスト
- 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) - Oja's Algorithm for Streaming Sparse PCA [7.059472280274011]
Oja's Algorithm for Streaming principal Component Analysis (PCA) for $n$ data-points in a $d$ dimensional space achieves the same sin-squared error $O(r_mathsfeff/n)$ as the offline algorithm in $O(d)$ space and $O(nd)$ time。
Ojaのアルゴリズムの出力をしきい値にする単純なシングルパス手順は、$O(d)$ space と $O(nd)$ time の正則性条件下での最小誤差を達成できることを示す。
論文 参考訳（メタデータ） (2024-02-11T16:36:48Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Learning linear dynamical systems under convex constraints [4.4351901934764975]
線形力学系を単一軌道の$T$サンプルから同定する問題を考察する。
A*$は、制約のない設定に必要な値よりも$T$小さい値を確実に見積もることができる。
論文 参考訳（メタデータ） (2023-03-27T11:49:40Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - 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) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳（メタデータ） (2021-03-29T23:03:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。