論文の概要: 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)
• 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)
• 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)

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

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