論文の概要: Sparsification for Sums of Exponentials and its Algorithmic Applications
- arxiv url: http://arxiv.org/abs/2106.02774v1
- Date: Sat, 5 Jun 2021 01:58:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-06-08 18:19:27.630023
- Title: Sparsification for Sums of Exponentials and its Algorithmic Applications
- Title（参考訳）: 指数関数和のスパーシフィケーションとそのアルゴリズムへの応用
- Authors: Jerry Li, Allen Liu, Ankur Moitra
- Abstract要約: 指数関数の和をスパース化するための新しい手法を導入し、様々なアルゴリズムを応用する。
周波数/成分数を$k' = widetildeO(k)$に減らし、対数係数に最適化する方法を示す。
- 参考スコア（独自算出の注目度）: 33.29641025468224
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Many works in signal processing and learning theory operate under the
assumption that the underlying model is simple, e.g. that a signal is
approximately $k$-Fourier-sparse or that a distribution can be approximated by
a mixture model that has at most $k$ components. However the problem of fitting
the parameters of such a model becomes more challenging when the
frequencies/components are too close together.
In this work we introduce new methods for sparsifying sums of exponentials
and give various algorithmic applications. First we study Fourier-sparse
interpolation without a frequency gap, where Chen et al. gave an algorithm for
finding an $\epsilon$-approximate solution which uses $k' = \mbox{poly}(k, \log
1/\epsilon)$ frequencies. Second, we study learning Gaussian mixture models in
one dimension without a separation condition. Kernel density estimators give an
$\epsilon$-approximation that uses $k' = O(k/\epsilon^2)$ components. These
methods both output models that are much more complex than what we started out
with. We show how to post-process to reduce the number of
frequencies/components down to $k' = \widetilde{O}(k)$, which is optimal up to
logarithmic factors. Moreover we give applications to model selection. In
particular, we give the first algorithms for approximately (and robustly)
determining the number of components in a Gaussian mixture model that work
without a separation condition.
- Abstract（参考訳）: 信号処理と学習理論の多くの研究は、基礎となるモデルが単純であるという仮定の下で行われる。
信号が約$k$-Fourier-sparseであること、あるいは分布が少なくとも$k$の成分を持つ混合モデルによって近似可能であること。
しかし、これらのモデルのパラメータを適合させる問題は、周波数/成分が近すぎるとより困難になる。
本研究では指数関数の和をスパース化し、様々なアルゴリズム的応用を与える新しい方法を提案する。
まず、Chenらによる周波数ギャップのないフーリエスパース補間について検討する。
k' = \mbox{poly}(k, \log 1/\epsilon)$周波数を使用する$\epsilon$-approximate の解を見つけるアルゴリズムを与えた。
第2に,分離条件のない1次元ガウス混合モデルの学習について検討する。
カーネル密度推定器は$k' = O(k/\epsilon^2)$コンポーネントを使用する$\epsilon$-approximationを与える。
これらのメソッドはどちらも、私たちが始めたものよりもずっと複雑なモデルを出力します。
周波数/成分数を$k' = \widetilde{O}(k)$に減らし、対数因子に最適化する方法を示す。
さらに、モデル選択へのアプリケーションも提供します。
特に、分離条件なしで機能するガウス混合モデルにおいて、およそ(かつ頑健に)成分数を決定するための最初のアルゴリズムを与える。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - A Unified Framework for Uniform Signal Recovery in Nonlinear Generative
Compressed Sensing [68.80803866919123]
非線形測定では、ほとんどの先行結果は一様ではない、すなわち、すべての$mathbfx*$に対してではなく、固定された$mathbfx*$に対して高い確率で保持される。
本フレームワークはGCSに1ビット/一様量子化観測と単一インデックスモデルを標準例として適用する。
また、指標集合が計量エントロピーが低い製品プロセスに対して、より厳密な境界を生み出す濃度不等式も開発する。
論文 参考訳（メタデータ） (2023-09-25T17:54:19Z) - Sparse Gaussian Graphical Models with Discrete Optimization:
Computational and Statistical Perspectives [8.403841349300103]
本研究では,無向ガウス図形モデルに基づくスパースグラフの学習問題を考察する。
擬似微分関数の $ell_0$-penalized バージョンに基づく新しい推定器 GraphL0BnB を提案する。
実/合成データセットに関する数値実験により,本手法がほぼ最適に,p = 104$の問題を解けることが示唆された。
論文 参考訳（メタデータ） (2023-07-18T15:49:02Z) - A Spectral Algorithm for List-Decodable Covariance Estimation in
Relative Frobenius Norm [41.03423042792559]
我々は、相対的なフロベニウスノルムにおいて、$Sigma$に近い仮説のリストを作成する。
結論として,ガウス混合モデルのロバストな部分クラスタリングのための効率的なスペクトルアルゴリズムを得る。
提案手法は, GMM を頑健に学習する最初の Sum-of-Squares-free アルゴリズムである。
論文 参考訳（メタデータ） (2023-05-01T17:54:35Z) - A Fourier Approach to Mixture Learning [46.995354373649675]
d = O(log k/loglog k)$ dimensions under separation $d/sqrtlog k (modulo factor)。
我々の結果は、分布のフーリエスペクトルの穏やかな条件の下で、非ガウス分布の混合を学習するために容易に拡張できる。
論文 参考訳（メタデータ） (2022-10-05T17:35:46Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Tight Bounds on the Hardness of Learning Simple Nonparametric Mixtures [9.053430799456587]
有限混合系における非パラメトリック分布の学習問題について検討する。
このようなモデルにおける成分分布を学習するために、サンプルの複雑さに厳密な境界を定めている。
論文 参考訳（メタデータ） (2022-03-28T23:53:48Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
本研究では,高次元ガウス混合系の対向ロバスト条件下での効率的な学習性について検討する。
理論的に最適に近い誤り証明である$tildeO(epsilon)$の情報を、$epsilon$-corrupted $k$-mixtureで学習するアルゴリズムを提供する。
我々の主な技術的貢献は、ガウス混合系からの新しい頑健な識別可能性証明クラスターであり、これは正方形の定度証明システムによって捉えることができる。
論文 参考訳（メタデータ） (2020-05-13T16:44:12Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。