論文の概要: Tractable downfall of basis pursuit in structured sparse optimization

• arxiv url: http://arxiv.org/abs/2503.19126v1
• Date: Mon, 24 Mar 2025 20:27:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-26 16:54:41.552524
• Title: Tractable downfall of basis pursuit in structured sparse optimization
• Title（参考訳）: 構造的スパース最適化における基底追跡のトラクタブルダウンフォール
• Authors: Maya V. Marmary, Christian Grussler,
• Abstract要約: 本稿では,線形下決定方程式系における最短解を求める問題について検討する。 特に、発見不可能な非ゼロ成分を解の最も小さい特異性に対応することができる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: The problem of finding the sparsest solution to a linear underdetermined system of equations, as it often appears in data analysis, optimal control and system identification problems, is considered. This non-convex problem is commonly solved by convexification via $\ell_1$-norm minimization, also known as basis pursuit. In this work, a class of structured matrices, representing the system of equations, is introduced for which the basis pursuit approach tractably fails to recover the sparsest solution. In particular, we are able to identify matrix columns that correspond to unrecoverable non-zero entries of the sparsest solution, as well as to conclude the uniqueness of the sparsest solution in polynomial time. These deterministic guarantees contrast popular probabilistic ones, and as such, provide valuable insights into the a priori design of sparse optimization problems. As our matrix structure appears naturally in optimal control problems, we exemplify our findings by showing that it is possible to verify a priori that basis pursuit may fail in finding fuel optimal regulators for a class of discrete-time linear time-invariant systems.
• Abstract（参考訳）: データ解析や最適制御,システム同定問題などによく見られるような,線形下決定方程式系に対する最も遠い解を求める問題について考察する。 この非凸問題は、基底探索としても知られる$\ell_1$-norm最小化によって、一般に凸化によって解決される。 本研究では, 方程式系を表す構造行列のクラスを導入し, 基礎探索法が難易度の高い解の回復に失敗する。 特に、最短解の発見不可能な非零成分に対応する行列列を特定でき、また、最短解の特異性を多項式時間で結論付けることができる。 これらの決定論的保証は、一般的な確率論的保証とは対照的であり、スパース最適化問題の事前設計に関する貴重な洞察を提供する。 最適制御問題では行列構造が自然に現れるため, 離散時間線形時間不変系の燃料最適レギュレータの発見において, 基準追従が失敗する可能性のある優先性を検証することが可能であることを示して, 知見を実証する。

関連論文リスト

• Feature selection in linear SVMs via a hard cardinality constraint: a scalable SDP decomposition approach [3.7876216422538485]
  本稿では, 線形支援ベクトルマシン(SVM)において, 濃度制約が適用された場合の組込み特徴選択問題について検討する。 この問題は、元の線形SVMが時間内に解決可能な問題に等しいにもかかわらず、濃度制約が存在するためNPハードである。 この問題に対処するために、まず2つの混合整数式を導入し、新しい半定緩和法を提案する。
  論文  参考訳（メタデータ） (2024-04-15T19:15:32Z)
• Orthogonally weighted $\ell_{2,1}$ regularization for rank-aware joint sparse recovery: algorithm and analysis [7.7001263654719985]
  我々は,新たな正規化法である $ell_2,1$$(mathitowell_2,1$) を用いて,結合スパース回復問題の効率的な解法を提案し,解析する。 この手法は特徴抽出、行列列選択、辞書学習に応用され、一般的な$ell_2,1$正規化とは異なる。 提案手法のランク認識の証明を行い,提案手法の最適化問題に対する解が存在することを証明し,収束を解析した効率的な解法を開発した。
  論文  参考訳（メタデータ） (2023-11-21T01:52:15Z)
• Discretize Relaxed Solution of Spectral Clustering via a Non-Heuristic Algorithm [77.53604156112144]
  我々は、元の問題と離散化アルゴリズムを橋渡しする1次項を開発する。 非ヒューリスティック法は元のグラフ切断問題を認識しているため、最終的な離散解の方が信頼性が高い。
  論文  参考訳（メタデータ） (2023-10-19T13:57:38Z)
• Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stability [107.65337427333064]
  AUPRC(Area Under the Precision-Recall Curve)の最適化は、機械学習にとって重要な問題である。 本研究では, AUPRC最適化の単依存一般化における最初の試行について述べる。 3つの画像検索データセットの実験は、我々のフレームワークの有効性と健全性に言及する。
  論文  参考訳（メタデータ） (2022-09-27T09:06:37Z)
• Large-scale matrix optimization based multi microgrid topology design with a constrained differential evolution algorithm [30.792124441010447]
  非線形問題を解くために二項行列に基づく微分進化アルゴリズムを提案する。 制約に対処するため,環境選択戦略を改良した実現可能性ルールを提案する。
  論文  参考訳（メタデータ） (2022-07-18T00:35:29Z)
• Sparse Quadratic Optimisation over the Stiefel Manifold with Application to Permutation Synchronisation [71.27989298860481]
  二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。 そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-09-30T19:17:35Z)
• Solving weakly supervised regression problem using low-rank manifold regularization [77.34726150561087]
  我々は弱い教師付き回帰問題を解く。 weakly"の下では、いくつかのトレーニングポイントではラベルが知られ、未知のものもあれば、無作為なノイズの存在やリソースの欠如などの理由によって不確かであることが分かっています。 数値的な節ではモンテカルロモデルを用いて提案手法を人工と実のデータセットに適用した。
  論文  参考訳（メタデータ） (2021-04-13T23:21:01Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  再構成誤差を$l_2,p$ノルム正規化と組み合わせることで,単純かつ効率的な特徴選択手法を提案する。 提案する非教師付きモデルを解くための効率的な最適化アルゴリズムを提案し,アルゴリズムの収束と計算の複雑さを理論的に解析する。
  論文  参考訳（メタデータ） (2020-12-29T04:08:38Z)
• Accelerated Sparse Bayesian Learning via Screening Test and Its Applications [0.9916217495995309]
  線形系では、過度に完備な特徴の辞書を具備した最小の解を求めるのは通常NPハードである。 本稿では,解の空間性を促進するためにパラメータ化を事前に用いた疎ベイズ学習を提案する。
  論文  参考訳（メタデータ） (2020-07-08T10:21:56Z)
• Eigendecomposition-Free Training of Deep Networks for Linear Least-Square Problems [107.3868459697569]
  我々は、ディープネットワークのトレーニングに固有分解のないアプローチを導入する。 この手法は固有分解の明示的な微分よりもはるかに堅牢であることを示す。 我々の手法は収束特性が良く、最先端の結果が得られます。
  論文  参考訳（メタデータ） (2020-04-15T04:29:34Z)

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

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