論文の概要: Compressed Sensing: A Discrete Optimization Approach
- arxiv url: http://arxiv.org/abs/2306.04647v2
- Date: Tue, 22 Aug 2023 21:06:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-24 17:58:28.340170
- Title: Compressed Sensing: A Discrete Optimization Approach
- Title(参考訳): Compressed Sensing:離散最適化アプローチ
- Authors: Dimitris Bertsimas and Nicholas A. G. Johnson
- Abstract要約: 圧縮センシング(CS)問題(Compressed Sensing, CS)は、線形測定の集合をある程度の数値耐性まで満たす最もスパースなベクトルを見つける問題である。
CSは、信号処理、データ圧縮、画像再構成などのアプリケーションで発生する統計学、オペレーションリサーチ、機械学習において中心的な問題である。
- 参考スコア(独自算出の注目度): 6.943816076962257
- 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. CS is a central problem in Statistics, Operations Research
and Machine Learning which arises in applications such as signal processing,
data compression and image reconstruction. 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 instances of CS to certifiable optimality. Our
numerical results show that our approach produces solutions that are on average
$6.22\%$ more sparse than solutions returned by state of the art benchmark
methods on synthetic data in minutes. 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, while for a given sparsity
level our approach produces solutions that have on average $10.77\%$ lower
reconstruction error than benchmark methods in minutes.
- Abstract(参考訳): 圧縮センシング(CS: Compressed Sensing)問題について検討した。これは,線形測定の集合をある程度の数値耐性まで満足する最もスパースなベクトルを求める問題である。
csは、信号処理、データ圧縮、画像再構成などのアプリケーションで発生する統計、運用研究、機械学習における中心的な問題である。
我々は,混合整数二階コーンプログラムとして再構成したcsの$\ell_2$正規化式を導入する。
この問題の2次円錐緩和を導出し、正規化パラメータの穏やかな条件下では、結果として得られる緩和は、よく研究された基礎追従問題と等価であることを示す。
本稿では,2次コーン緩和を強化し,2次コーン緩和を利用した独自の分岐結合アルゴリズムを開発し,CSのインスタンスを最適性を証明する。
数値的な結果から,本手法は,合成データに対する art ベンチマーク手法によって得られた解よりも平均 6.22\% 少ない解を数分で生成できることがわかった。
実世界のECGデータでは、与えられた$\ell_2$リコンストラクションエラーに対して、我々のアプローチはベンチマークメソッドよりも平均9.95\%$スパースなソリューションを生成し、一方、所定の空間レベルでは平均10.77\%$リコンストラクションエラーを数分で生成する。
関連論文リスト
- Convex Relaxations of ReLU Neural Networks Approximate Global Optima in
Polynomial Time [54.01594785269913]
本稿では, 重み劣化と凸緩和に則った2層ReLUネットワーク間の最適性ギャップについて述べる。
トレーニングデータがランダムである場合、元の問題と緩和の間の相対的な最適性ギャップは、サンプルの勾配によって境界付けられることを示す。
論文 参考訳(メタデータ) (2024-02-06T01:29:35Z) - Polynomial-Time Solutions for ReLU Network Training: A Complexity
Classification via Max-Cut and Zonotopes [70.52097560486683]
我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。
特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
論文 参考訳(メタデータ) (2023-11-18T04:41:07Z) - Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression [20.00109111254507]
この問題は、$frackSNR2$-to-$frack2SNR2$statistic-to-computational gapである。
また,この問題が困難な狭い状況以外では,関連する混合回帰検出問題を解くための簡単なしきい値決定アルゴリズムも分析する。
論文 参考訳(メタデータ) (2023-03-03T18:03:49Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Distributed Sparse Regression via Penalization [5.990069843501885]
エージェントのネットワーク上の線形回帰を、(集中ノードを持たない)無向グラフとしてモデル化する。
推定問題は、局所的なLASSO損失関数の和とコンセンサス制約の2次ペナルティの最小化として定式化される。
本稿では, ペナル化問題に適用した近似勾配アルゴリズムが, 集中的な統計的誤差の順序の許容値まで線形に収束することを示す。
論文 参考訳(メタデータ) (2021-11-12T01:51:50Z) - Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization
Approach [6.952045528182883]
スパースプラス低ランク分解問題(SLR)について検討する。
SLRはオペレーションリサーチと機械学習の基本的な問題である。
本稿では,SLRの新たな定式化を導入し,その基礎となる離散性をモデル化する。
論文 参考訳(メタデータ) (2021-09-26T20:49:16Z) - Slowly Varying Regression under Sparsity [5.22980614912553]
本稿では, 緩やかな過度回帰の枠組みを提示し, 回帰モデルが緩やかかつスパースな変動を示すようにした。
本稿では,バイナリ凸アルゴリズムとして再構成する手法を提案する。
結果として得られたモデルは、様々なデータセット間で競合する定式化よりも優れていることを示す。
論文 参考訳(メタデータ) (2021-02-22T04:51:44Z) - Combining Deep Learning and Optimization for Security-Constrained
Optimal Power Flow [94.24763814458686]
セキュリティに制約のある最適電力フロー(SCOPF)は、電力システムの基本である。
SCOPF問題におけるAPRのモデル化は、複雑な大規模混合整数プログラムをもたらす。
本稿では,ディープラーニングとロバスト最適化を組み合わせた新しい手法を提案する。
論文 参考訳(メタデータ) (2020-07-14T12:38:21Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳(メタデータ) (2020-07-10T05:20:02Z) - 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) - Sparse Regression at Scale: Branch-and-Bound rooted in First-Order
Optimization [6.037383467521294]
我々は $ell_0$ 正規化回帰のための新しい正確な MIP フレームワークを提案する。
私たちのフレームワークは、$p sim 107$までスケールでき、少なくとも5,000$xのスピードアップを達成できます。
実装をツールキットL0BnBでオープンソースにしています。
論文 参考訳(メタデータ) (2020-04-13T18:45:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。