論文の概要: WARPd: A linearly convergent first-order method for inverse problems
with approximate sharpness conditions
- arxiv url: http://arxiv.org/abs/2110.12437v1
- Date: Sun, 24 Oct 2021 13:19:41 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-26 15:46:36.004462
- Title: WARPd: A linearly convergent first-order method for inverse problems
with approximate sharpness conditions
- Title(参考訳): WARPd:近似シャープネス条件をもつ逆問題に対する線形収束一階法
- Authors: Matthew J. Colbrook
- Abstract要約: シャープネス条件は1次法のリスタートスキームのリカバリ性能を直接制御する。
重み付き, 加速度付き, 再起動されたプリマルデュアル(WARPd)の1次手法を提案する。
一般的な近似的シャープネス条件の下では、WARPd は所望のベクトルに対して安定な線形収束を達成する。
本稿では、WARPdが専門的な最先端手法と比較し、大規模問題の解決に最適であることを示す。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reconstruction of signals from undersampled and noisy measurements is a topic
of considerable interest. Sharpness conditions directly control the recovery
performance of restart schemes for first-order methods without the need for
restrictive assumptions such as strong convexity. However, they are challenging
to apply in the presence of noise or approximate model classes (e.g.,
approximate sparsity). We provide a first-order method: Weighted, Accelerated
and Restarted Primal-dual (WARPd), based on primal-dual iterations and a novel
restart-reweight scheme. Under a generic approximate sharpness condition, WARPd
achieves stable linear convergence to the desired vector. Many problems of
interest fit into this framework. For example, we analyze sparse recovery in
compressed sensing, low-rank matrix recovery, matrix completion, TV
regularization, minimization of $\|Bx\|_{l^1}$ under constraints
($l^1$-analysis problems for general $B$), and mixed regularization problems.
We show how several quantities controlling recovery performance also provide
explicit approximate sharpness constants. Numerical experiments show that WARPd
compares favorably with specialized state-of-the-art methods and is ideally
suited for solving large-scale problems. We also present a noise-blind variant
based on the Square-Root LASSO decoder. Finally, we show how to unroll WARPd as
neural networks. This approximation theory result provides lower bounds for
stable and accurate neural networks for inverse problems and sheds light on
architecture choices. Code and a gallery of examples are made available online
as a MATLAB package.
- Abstract(参考訳): アンダーサンプルとノイズ測定による信号の再構成は、かなりの関心を集めている。
シャープネス条件は、強い凸性のような制限的な仮定を必要とせずに、一階法の再起動スキームの回復性能を直接制御する。
しかし、ノイズや近似モデルクラス(例えば、近似空間)の存在下で適用することは困難である。
プライマル・デュアル・イテレーションと新しいリスタート・リウェイト・スキームに基づいて、ウェイトド、アクセラレーション、リスタートされたプライマル・ダイアル(WARPd)を提案する。
一般的な近似シャープネス条件の下で、WARPd は所望のベクトルに対して安定な線型収束を達成する。
多くの問題がこの枠組みに当てはまる。
例えば、圧縮センシングにおけるスパース回復、低ランクマトリクス回復、マトリクス完全化、テレビ正規化、制約下での$\|bx\|_{l^1}$の最小化(l^1$- analysis problem for general $b$)、混合正規化問題などを分析する。
本稿では,回復性能を制御する数量を明示的な近似シャープネス定数として与える方法を示す。
数値実験により、WARPdは特定の最先端手法と好適に比較でき、大規模問題の解法に最適であることが示された。
また、Square-Root LASSOデコーダに基づくノイズブラインド版を提案する。
最後に、WARPdをニューラルネットワークとしてアンロールする方法を示す。
この近似理論の結果は、逆問題に対する安定かつ正確なニューラルネットワークの低い境界を提供し、アーキテクチャの選択に光を当てる。
コードとサンプルのギャラリーは、MATLABパッケージとしてオンラインで公開されている。
関連論文リスト
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time [54.01594785269913]
本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳(メタデータ) (2023-10-20T12:45:12Z) - Restarts subject to approximate sharpness: A parameter-free and optimal
scheme for first-order methods [2.513785998932353]
シャープネス(Sharpness)は、目的関数の準最適性によってミニマからの距離を束縛する連続最適化における仮定である。
シャープネスは、通常不明な問題固有の定数を伴い、以前の再起動スキームは収束率を減少させる。
対象関数の誤差に未知の定数摂動を組み込んだシャープネスの一般化である近似シャープネスの仮定を考察する。
論文 参考訳(メタデータ) (2023-01-05T19:01:41Z) - Retire: Robust Expectile Regression in High Dimensions [3.9391041278203978]
ペナル化量子化法と期待回帰法は、高次元データの異方性検出に有用な手段を提供する。
我々は,頑健な期待回帰(退職)を提案し,研究する。
提案手法は半平滑なニュートン座標降下アルゴリズムにより効率よく解けることを示す。
論文 参考訳(メタデータ) (2022-12-11T18:03:12Z) - Restricted Strong Convexity of Deep Learning Models with Smooth
Activations [31.003601717265006]
本研究では,スムーズなアクティベーション機能を持つディープラーニングモデルの最適化問題について検討する。
Restricted Strong Convexity (RSC) に基づく最適化の新しい解析手法を提案する。
深層学習モデルのためのRCCに基づくGDの幾何収束性を確立するための最初の結果である。
論文 参考訳(メタデータ) (2022-09-29T21:24:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳(メタデータ) (2022-08-11T04:12:50Z) - Alternating minimization for generalized rank one matrix sensing: Sharp
predictions from a random initialization [10.516962652888989]
ランクランダム行列の特性をdで推定する手法を示す。
鋭い収束は、単一のステップで正確な回復を保証する。
我々の分析は、この問題の他のいくつかの特性も明らかにしている。
論文 参考訳(メタデータ) (2022-07-20T05:31:05Z) - Statistical Inference of Constrained Stochastic Optimization via
Sketched Sequential Quadratic Programming [59.36379287247961]
この問題を解決するために,完全オンライン逐次2次プログラミング(StoSQP)手法を開発した。
最近の数値二階法の設計により、StoSQPは任意のランダムなステップサイズを適応的に選択できる。
また,2次法の計算コストを大幅に削減するため,StoSQPはランダム化反復解法を用いて2次プログラムを不正確に解けるようにした。
論文 参考訳(メタデータ) (2022-05-27T00:34:03Z) - Distributional Hardness Against Preconditioned Lasso via Erasure-Robust
Designs [22.41443027099101]
標準スパースランダム設計は, 逆測定消去に対して高い確率で頑健であることを示す。
消去下での任意のスパース信号の部分的回復性が圧縮センシングで研究されたのはこれが初めてである。
論文 参考訳(メタデータ) (2022-03-05T22:16:05Z) - Optimal Online Generalized Linear Regression with Stochastic Noise and
Its Application to Heteroscedastic Bandits [88.6139446295537]
一般化線形モデルの設定におけるオンライン一般化線形回帰の問題について検討する。
ラベルノイズに対処するため、古典的追従正規化リーダ(FTRL)アルゴリズムを鋭く解析する。
本稿では,FTRLに基づくアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-28T08:25:26Z) - Graph Signal Restoration Using Nested Deep Algorithm Unrolling [85.53158261016331]
グラフ信号処理は、センサー、社会交通脳ネットワーク、ポイントクラウド処理、グラフネットワークなど、多くのアプリケーションにおいてユビキタスなタスクである。
凸非依存型深部ADMM(ADMM)に基づく2つの復元手法を提案する。
提案手法のパラメータはエンドツーエンドでトレーニング可能である。
論文 参考訳(メタデータ) (2021-06-30T08:57:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。