論文の概要: Compressed Sensing: A Discrete Optimization Approach

• arxiv url: http://arxiv.org/abs/2306.04647v3
• Date: Fri, 12 Jul 2024 03:46:02 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-16 05:56:40.173290
• Title: Compressed Sensing: A Discrete Optimization Approach
• Title（参考訳）: Compressed Sensing:離散最適化アプローチ
• Authors: Dimitris Bertsimas, Nicholas A. G. Johnson,
• Abstract要約: 本稿では, 2次円錐緩和を強化し, 独自の分岐結合アルゴリズムを開発する半定緩和法を提案する。 マルチラベル分類アルゴリズムの構成要素として用いられる場合,提案手法は,ベンチマーク圧縮センシング法よりも高い分類精度を実現する。
• 参考スコア（独自算出の注目度）: 5.877778007271621
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the Compressed Sensing (CS) problem, which is the problem of finding the most sparse vector that satisfies a set of linear measurements up to some numerical tolerance. We introduce an $\ell_2$ regularized formulation of CS which we reformulate as a mixed integer second order cone program. We derive a second order cone relaxation of this problem and show that under mild conditions on the regularization parameter, the resulting relaxation is equivalent to the well studied basis pursuit denoising problem. We present a semidefinite relaxation that strengthens the second order cone relaxation and develop a custom branch-and-bound algorithm that leverages our second order cone relaxation to solve small-scale instances of CS to certifiable optimality. When compared against solutions produced by three state of the art benchmark methods on synthetic data, our numerical results show that our approach produces solutions that are on average $6.22\%$ more sparse. When compared only against the experiment-wise best performing benchmark method on synthetic data, our approach produces solutions that are on average $3.10\%$ more sparse. On real world ECG data, for a given $\ell_2$ reconstruction error our approach produces solutions that are on average $9.95\%$ more sparse than benchmark methods ($3.88\%$ more sparse if only compared against the best performing benchmark), while for a given sparsity level our approach produces solutions that have on average $10.77\%$ lower reconstruction error than benchmark methods ($1.42\%$ lower error if only compared against the best performing benchmark). When used as a component of a multi-label classification algorithm, our approach achieves greater classification accuracy than benchmark compressed sensing methods. This improved accuracy comes at the cost of an increase in computation time by several orders of magnitude.
• Abstract（参考訳）: 圧縮センシング(CS: Compressed Sensing)問題について検討した。これは,線形測定の集合をある程度の数値耐性まで満足する最もスパースなベクトルを求める問題である。 混合整数二階円錐プログラムとして再構成したCSの正規化式を$\ell_2$で導入する。 この問題の2次円錐緩和を導出し、正規化パラメータの穏やかな条件下では、結果として得られる緩和は、よく研究された基礎追従問題と等価であることを示す。 本稿では,2次円錐緩和を強化し,2次円錐緩和を利用してCSの小規模インスタンスを証明可能な最適性に解決する独自の分岐結合アルゴリズムを提案する。 合成データに対する3つの最先端ベンチマーク手法による解と比較すると,我々の手法は平均6.22 %$sparseの解を生成することがわかった。 合成データに対して実験的に最も優れたベンチマーク法と比較した場合、我々の手法は平均3.10\%$よりスパースな解を生成する。 実世界のECGデータでは、与えられた$\ell_2$リコンストラクションエラーに対して、我々のアプローチは、ベンチマークメソッドよりも平均9.95\%$スパースなソリューション(最高のパフォーマンスベンチマークと比較してみれば3.88\%$スパース)を生成し、一方、与えられたスパーシティレベルでは、ベンチマークメソッドよりも平均10.77\%$低いリコンストラクションエラー(最高のパフォーマンスベンチマークと比較してみれば1.42\%$低いエラー)を生成する。 マルチラベル分類アルゴリズムの構成要素として用いられる場合,提案手法は,ベンチマーク圧縮センシング法よりも高い分類精度を実現する。 この改良された精度は、数桁の計算時間の増加によるコストが伴う。

関連論文リスト

• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Robust Second-Order Nonconvex Optimization and Its Application to Low Rank Matrix Sensing [47.32366699399839]
  近似第二エピシロン依存(SOSP)の発見は、よく研究され基礎的な問題である。 本稿では,低次元センサマシン最適化問題に適用する。
  論文  参考訳（メタデータ） (2024-03-12T01:27:44Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• Near Optimal Private and Robust Linear Regression [47.2888113094367]
  本稿では,2つのアルゴリズムを改良したDP-SGDアルゴリズムを提案する。 ラベル破壊の下では、これは$(varepsilon,delta)$-DPとロバスト性の両方を保証する最初の効率的な線形回帰アルゴリズムである。
  論文  参考訳（メタデータ） (2023-01-30T20:33:26Z)
• Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
  我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。 提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
  論文  参考訳（メタデータ） (2022-10-23T21:24:37Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach [6.952045528182883]
  スパースプラス低ランク分解問題(SLR)について検討する。 SLRはオペレーションリサーチと機械学習の基本的な問題である。 本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
  論文  参考訳（メタデータ） (2021-09-26T20:49:16Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。 我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
  論文  参考訳（メタデータ） (2021-03-04T19:01:20Z)
• Least Squares Regression with Markovian Data: Fundamental Limits and Algorithms [69.45237691598774]
  マルコフ連鎖からデータポイントが依存しサンプリングされる最小二乗線形回帰問題について検討する。 この問題を$tau_mathsfmix$という観点から、鋭い情報理論のミニマックス下限を確立する。 本稿では,経験的リプレイに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-16T04:26:50Z)
• Learning Sparse Classifiers: Continuous and Mixed Integer Optimization Perspectives [10.291482850329892]
  混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。 数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。 さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
  論文  参考訳（メタデータ） (2020-01-17T18:47:02Z)

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

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