論文の概要: Exact and efficient basis pursuit denoising via differential inclusions and a selection principle

• arxiv url: http://arxiv.org/abs/2507.05562v1
• Date: Tue, 08 Jul 2025 01:07:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-09 16:34:37.464554
• Title: Exact and efficient basis pursuit denoising via differential inclusions and a selection principle
• Title（参考訳）: 差分包摂と選択原理による厳密かつ効率的な基本探索
• Authors: Gabriel P. Langlois, Jérôme Darbon,
• Abstract要約: そこで本研究では,差分包摂を用いたBPDN(base pursue denoising)の高精度かつ効率的なアルゴリズムを提案する。 我々の分析は自然に機械の精度まで数値的に正確なアルゴリズムを導き出す。 数値実験により,本アルゴリズムは精度と効率の両方で最先端のアルゴリズムより優れていることを確認した。
• 参考スコア（独自算出の注目度）: 0.3222802562733786
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Basis pursuit denoising (BPDN) is a cornerstone of compressive sensing, statistics and machine learning. While various algorithms for BPDN have been proposed, they invariably suffer from drawbacks and must either favor efficiency at the expense of accuracy or vice versa. As such, state-of-the-art algorithms remain ineffective for high-dimensional applications that require accurate solutions within a reasonable amount of computational time. In this work, we address this issue and propose an exact and efficient algorithm for BPDN using differential inclusions. Specifically, we prove that a selection principle from the theory of differential inclusions turns the dual problem of BPDN into calculating the trajectory of an \emph{integrable} projected dynamical system, that is, whose trajectory and asymptotic limit can be computed exactly. Our analysis naturally yields an exact algorithm, numerically up to machine precision, that is amenable to computing regularization paths and very fast. Numerical experiments confirm that our algorithm outperforms the state-of-the-art algorithms in both accuracy and efficiency. Moreover, we show that the global continuation of solutions (in terms of the hyperparameter and data) of the projected dynamical system yields a rigorous homotopy algorithm for BPDN, as well as a novel greedy algorithm for computing feasible solutions to basis pursuit in strongly polynomial time. Beyond this work, we expect that our results and analysis can be adapted to compute exact or approximate solutions to a broader class of polyhedral-constrained optimization problems.
• Abstract（参考訳）: BPDN(Basis pursue denoising)は、圧縮センシング、統計、機械学習の基礎である。 BPDNの様々なアルゴリズムが提案されているが、必ず欠点に悩まされ、精度を犠牲にして効率を優先しなければならない。 したがって、最先端のアルゴリズムは、妥当な計算時間内に正確な解を必要とする高次元のアプリケーションには効果がない。 本研究では,この問題に対処し,差分包摂を用いたBPDNの正確かつ効率的なアルゴリズムを提案する。 具体的には、微分包含理論からの選択原理が、BPDNの双対問題から射影された力学系の軌道を計算すること、すなわち、軌道と漸近極限を正確に計算できることを証明する。 我々の分析は自然に機械の精度まで正確なアルゴリズムをもたらし、それは正規化パスの計算に適しており、非常に高速である。 数値実験により,本アルゴリズムは精度と効率の両方で最先端のアルゴリズムより優れていることを確認した。 さらに、予測された力学系の解の(ハイパーパラメータとデータの観点から)大域的な連続性は、BPDNの厳密なホモトピーアルゴリズムと、強い多項式時間で基底追従する実現可能な解を計算するための新しいグリーディアルゴリズムをもたらすことを示す。 この研究の他に、我々の結果と分析は、より広範な多面体制約付き最適化問題に対する正確な解や近似解の計算に適応できることを期待している。

関連論文リスト

• Towards minimax optimal algorithms for Active Simple Hypothesis Testing [0.0]
  固定予算ベストアーム識別問題の簡易な変種である能動簡易仮説テスト(ASHT)問題について検討した。 ASHT問題の上界の新たなゲーム理論の定式化を提供する。 本稿では,前処理に比べて計算能力に優れた近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-26T20:03:53Z)
• WENDy for Nonlinear-in-Parameters ODEs [1.9573380763700712]
  WEN(Wak-form Estimation of Non-linear Dynamics)は、非線形インである通常の微分方程式の系に対応するために拡張される。 提案手法の実用的メリットを実証するために,一連のベンチマークシステムに結果を提示する。
  論文  参考訳（メタデータ） (2025-02-13T01:40:21Z)
• Efficient Convex Algorithms for Universal Kernel Learning [46.573275307034336]
  カーネルの理想的な集合: 線形パラメータ化(トラクタビリティ)を認める; すべてのカーネルの集合に密着する(正確性)。 従来のカーネル最適化アルゴリズムは分類に限られており、計算に複雑なセミデフィニティプログラミング(SDP)アルゴリズムに依存していた。 本稿では,従来のSDP手法と比較して計算量を大幅に削減するSVD-QCQPQPアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-15T04:57:37Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [61.98523595657983]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Amortized Implicit Differentiation for Stochastic Bilevel Optimization [53.12363770169761]
  決定論的条件と決定論的条件の両方において、二段階最適化問題を解決するアルゴリズムのクラスについて検討する。 厳密な勾配の推定を補正するために、ウォームスタート戦略を利用する。 このフレームワークを用いることで、これらのアルゴリズムは勾配の偏りのない推定値にアクセス可能な手法の計算複雑性と一致することを示す。
  論文  参考訳（メタデータ） (2021-11-29T15:10:09Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。 両レベル最適化のための2つの新しいアルゴリズムを提案する。 両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
  論文  参考訳（メタデータ） (2021-06-08T21:05:30Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Adaptivity of Stochastic Gradient Methods for Nonconvex Optimization [71.03797261151605]
  適応性は現代最適化理論において重要であるが、研究されていない性質である。 提案アルゴリズムは,PL目標に対して既存のアルゴリズムよりも優れた性能を保ちながら,PL目標に対して最適な収束性を実現することを実証した。
  論文  参考訳（メタデータ） (2020-02-13T05:42:27Z)
• Boosting Algorithms for Estimating Optimal Individualized Treatment Rules [4.898659895355356]
  最適な個別化処理規則を推定するための非パラメトリックアルゴリズムを提案する。 提案アルゴリズムは機械学習文学において最も強力なアルゴリズムの1つであるXGBoostアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2020-01-31T22:26:38Z)

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

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