論文の概要: Fast Algorithm for Constrained Linear Inverse Problems

• arxiv url: http://arxiv.org/abs/2212.01068v6
• Date: Wed, 24 Jan 2024 15:19:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-01-25 18:18:30.049499
• Title: Fast Algorithm for Constrained Linear Inverse Problems
• Title（参考訳）: 制約付き線形逆問題に対する高速アルゴリズム
• Authors: Mohammed Rayyan Sheriff, Floor Fenne Redel, Peyman Mohajerin Esfahani
• Abstract要約: 我々は、ある原子ノルムが2次制約の下で最小化される制約付き線形逆問題(LIP)を考える。 凸正則性を改善した制約付きLIPの2つの等価な再構成を提案する。 FLIPSの2成分選択,圧縮センシング,画像デノーミングの古典的問題に対する性能を実証する。
• 参考スコア（独自算出の注目度）: 5.0490573482829335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the constrained Linear Inverse Problem (LIP), where a certain atomic norm (like the $\ell_1 $ norm) is minimized subject to a quadratic constraint. Typically, such cost functions are non-differentiable which makes them not amenable to the fast optimization methods existing in practice. We propose two equivalent reformulations of the constrained LIP with improved convex regularity: (i) a smooth convex minimization problem, and (ii) a strongly convex min-max problem. These problems could be solved by applying existing acceleration-based convex optimization methods which provide better $ O \left( \frac{1}{k^2} \right) $ theoretical convergence guarantee, improving upon the current best rate of $ O \left( \frac{1}{k} \right) $. We also provide a novel algorithm named the Fast Linear Inverse Problem Solver (FLIPS), which is tailored to maximally exploit the structure of the reformulations. We demonstrate the performance of FLIPS on the classical problems of Binary Selection, Compressed Sensing, and Image Denoising. We also provide open source \texttt{MATLAB} package for these three examples, which can be easily adapted to other LIPs.
• Abstract（参考訳）: 制約付き線形逆問題(LIP)を考えると、ある原子ノルム(例えば$\ell_1 $ノルム)は二次的制約の対象として最小化される。 通常、そのようなコスト関数は微分不可能であり、実際に存在する高速な最適化手法には適用できない。 凸正則性を改善した制約付きLIPの2つの等価な再構成を提案する。 (i)滑らかな凸最小化問題、及び (ii) 強い凸 min-max 問題。 これらの問題は、より優れた$ O \left( \frac{1}{k^2} \right)$理論収束保証を提供する既存の加速に基づく凸最適化法を適用し、現在の最高値である$ O \left( \frac{1}{k} \right)$を改善することで解決できる。 また,修正構造を最大限に活用するために,FLIPS(Fast Linear Inverse Problem Solver)という新しいアルゴリズムも提案する。 FLIPSの2成分選択,圧縮センシング,画像デノーミングの古典的問題に対する性能を実証する。 また,これら3つの例に対して,オープンソース \texttt{MATLAB} パッケージを提供する。

関連論文リスト

• Methods for Convex $(L_0,L_1)$-Smooth Optimization: Clipping, Acceleration, and Adaptivity [50.25258834153574]
  我々は、(強に)凸 $(L0)$-smooth 関数のクラスに焦点を当て、いくつかの既存のメソッドに対する新しい収束保証を導出する。 特に,スムーズなグラディエント・クリッピングを有するグラディエント・ディフレッシュと,ポリアク・ステップサイズを有するグラディエント・ディフレッシュのコンバージェンス・レートの改善を導出した。
  論文  参考訳（メタデータ） (2024-09-23T13:11:37Z)
• An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
  下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。 我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
  論文  参考訳（メタデータ） (2024-02-12T22:34:53Z)
• Nonsmooth Projection-Free Optimization with Functional Constraints [12.20060970177791]
  本稿では,制約付き非平滑凸計算のための段階的アルゴリズムを提案する。 提案アルゴリズムは一般凸関数不等式制約で非滑らかな問題を扱うことができる。 決定論的下位段階が下位段階に置き換わる際にも同様のパフォーマンスが観察される。
  論文  参考訳（メタデータ） (2023-11-18T23:06:33Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• A Block Coordinate Descent Method for Nonsmooth Composite Optimization under Orthogonality Constraints [7.716156977428555]
  一般性制約を伴う非滑らかな複合最適化は、統計学習とデータ科学に幅広い応用がある。 textittextbfOBCDは非滑らかな複合問題を解くための新しいブロック座標法である。
  論文  参考訳（メタデータ） (2023-04-07T13:44:59Z)
• Gauges and Accelerated Optimization over Smooth and/or Strongly Convex Sets [4.5344287283782405]
  我々は、滑らかかつ/または強い凸集合上で定義される実現可能性および制約付き最適化問題を考察する。 これらの設定において,新しい拡張性,プロジェクションフリー,アクセラレーションファーストオーダー手法を提案する。
  論文  参考訳（メタデータ） (2023-03-09T05:05:54Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• A Simple yet Universal Strategy for Online Convex Optimization [97.64589722655612]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 鍵となるアイデアは、元のオンライン機能を処理する専門家のセットを構築し、emphlinearized lossの上にメタアゴリタムを配置することだ。 我々の戦略は、強い凸関数と指数関数のために設計された専門家の理論的保証を継承する。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)

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

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