論文の概要: Efficient Algorithms for Sparse Moment Problems without Separation

• arxiv url: http://arxiv.org/abs/2207.13008v2
• Date: Sun, 23 Jul 2023 04:52:37 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-26 00:59:15.910271
• Title: Efficient Algorithms for Sparse Moment Problems without Separation
• Title（参考訳）: 分離のないスパースモーメント問題の効率的なアルゴリズム
• Authors: Zhiyuan Fan and Jian Li
• Abstract要約: ノイズモーメント情報から高次元空間における$k$-spike混合を学習するスパースモーメント問題を考える。 以前のアルゴリズムは、特定の分離仮定を仮定するか、より多くのリカバリモーメントを使用するか、または(超)指数時間で実行します。 高次元の場合のアルゴリズムは、混合の1次元射影をランダムなベクトルと混合の2次元射影のセットに整列させることにより、各スパイクの座標を決定する。
• 参考スコア（独自算出の注目度）: 6.732901486505047
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the sparse moment problem of learning a $k$-spike mixture in high-dimensional space from its noisy moment information in any dimension. We measure the accuracy of the learned mixtures using transportation distance. Previous algorithms either assume certain separation assumptions, use more recovery moments, or run in (super) exponential time. Our algorithm for the one-dimensional problem (also called the sparse Hausdorff moment problem) is a robust version of the classic Prony's method, and our contribution mainly lies in the analysis. We adopt a global and much tighter analysis than previous work (which analyzes the perturbation of the intermediate results of Prony's method). A useful technical ingredient is a connection between the linear system defined by the Vandermonde matrix and the Schur polynomial, which allows us to provide tight perturbation bound independent of the separation and may be useful in other contexts. To tackle the high-dimensional problem, we first solve the two-dimensional problem by extending the one-dimensional algorithm and analysis to complex numbers. Our algorithm for the high-dimensional case determines the coordinates of each spike by aligning a 1d projection of the mixture to a random vector and a set of 2d projections of the mixture. Our results have applications to learning topic models and Gaussian mixtures, implying improved sample complexity results or running time over prior work.
• Abstract（参考訳）: 我々は,任意の次元の雑音モーメント情報から高次元空間におけるk$-spike混合の学習におけるスパースモーメント問題を考える。 移動距離を用いて学習した混合物の精度を測定する。 以前のアルゴリズムは、特定の分離仮定を仮定するか、より多くのリカバリモーメントを使用するか、あるいは(超)指数関数時間で実行する。 我々の一次元問題に対するアルゴリズム(スパースハウスドルフモーメント問題とも呼ばれる)は古典的なプロニーの手法の頑健なバージョンであり、我々の貢献は主に解析に関係している。 従来の研究(プロニーの手法の中間結果の摂動を解析する)よりも大域的かつより厳密な分析を採用する。 有用な技術的要素は、ヴァンダーモンド行列で定義される線形系とシュール多項式の間の接続であり、これは分離とは独立に束縛され、他の文脈で有用である。 この高次元問題に取り組むために,まず1次元アルゴリズムと解析を複素数に拡張して2次元問題を解く。 高次元の場合のアルゴリズムは、混合の1次元投影とランダムベクトルと混合の2次元投影のセットを整合させることにより、各スパイクの座標を決定する。 この結果から,トピックモデルとガウス混合の学習に応用でき,サンプル複雑性の改善や事前作業の時間短縮が期待できる。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Fast Optimal Locally Private Mean Estimation via Random Projections [58.603579803010796]
  ユークリッド球における高次元ベクトルの局所的プライベート平均推定の問題について検討する。 プライベート平均推定のための新しいアルゴリズムフレームワークであるProjUnitを提案する。 各ランダム化器はその入力をランダムな低次元部分空間に投影し、結果を正規化し、最適なアルゴリズムを実行する。
  論文  参考訳（メタデータ） (2023-06-07T14:07:35Z)
• Sublinear Time Algorithms for Several Geometric Optimization (With Outliers) Problems In Machine Learning [8.794896028549323]
  ユークリッド空間$mathbbRd$における最小閉球(MEB)問題を再考する。 本稿では,MEBの安定性の概念を紹介する。 安定仮定の下では、半径近似MEBの2つのサンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-07T15:03:45Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  共分散行列の明示的な反転を回避する新しいSBL推論アルゴリズムを導入する。 私たちの手法は、既存のベースラインよりも数千倍も高速です。 我々は,SBLが高次元信号回復問題に難なく対処できる新しいアルゴリズムについて紹介する。
  論文  参考訳（メタデータ） (2021-05-21T16:20:07Z)
• Analysis of Truncated Orthogonal Iteration for Sparse Eigenvector Problems [78.95866278697777]
  本研究では,多元的固有ベクトルを分散制約で同時に計算するTruncated Orthogonal Iterationの2つの変種を提案する。 次に,我々のアルゴリズムを適用して,幅広いテストデータセットに対するスパース原理成分分析問題を解く。
  論文  参考訳（メタデータ） (2021-03-24T23:11:32Z)
• PCA Reduced Gaussian Mixture Models with Applications in Superresolution [1.885698488789676]
  本稿は、このトピックに2倍のコントリビューションを提供する。 まず,モデルの各成分におけるデータ次元の減少と合わせてガウス混合モデルを提案する。 第2に,サンディープとヤコブのアプローチに基づく2次元および3次元材料画像の超解像化にPCA-GMMを適用した。
  論文  参考訳（メタデータ） (2020-09-16T07:33:56Z)
• Effective Dimension Adaptive Sketching Methods for Faster Regularized Least-Squares Optimization [56.05635751529922]
  スケッチに基づくL2正規化最小二乗問題の解法を提案する。 我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
  論文  参考訳（メタデータ） (2020-06-10T15:00:09Z)
• Efficient Algorithms for Multidimensional Segmented Regression [42.046881924063044]
  多次元回帰を用いた固定設計の基本問題について検討する。 我々は任意の固定次元におけるこの問題に対する最初のサンプルと計算効率のよいアルゴリズムを提供する。 提案アルゴリズムは,多次元的条件下では新規な,単純なマージ反復手法に依存している。
  論文  参考訳（メタデータ） (2020-03-24T19:39:34Z)
• Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
  このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。 我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。 得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
  論文  参考訳（メタデータ） (2020-02-21T17:45:32Z)

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

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