論文の概要: Coresets for Data Discretization and Sine Wave Fitting
- arxiv url: http://arxiv.org/abs/2203.03009v1
- Date: Sun, 6 Mar 2022 17:07:56 GMT
- ステータス: 処理完了
- システム内更新日: 2022-03-08 17:08:07.044719
- Title: Coresets for Data Discretization and Sine Wave Fitting
- Title（参考訳）: データ離散化のためのコアセットと正弦波フィッティング
- Authors: Alaa Maalouf and Murad Tukan and Eric Price and Daniel Kane and Dan
Feldman
- Abstract要約: N]:=1,cdots,N$の整数列は、センサから受信される。
目標は、これまでに受け取った$n$ポイントを1つの周波数で近似することである。
経験的集合 $P$ of $n$ が加重部分集合 $Ssubseteq P$ を持つことを証明している。
- 参考スコア（独自算出の注目度）: 39.18104905459739
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the \emph{monitoring} problem, the input is an unbounded stream
$P={p_1,p_2\cdots}$ of integers in $[N]:=\{1,\cdots,N\}$, that are obtained
from a sensor (such as GPS or heart beats of a human). The goal (e.g., for
anomaly detection) is to approximate the $n$ points received so far in $P$ by a
single frequency $\sin$, e.g. $\min_{c\in C}cost(P,c)+\lambda(c)$, where
$cost(P,c)=\sum_{i=1}^n \sin^2(\frac{2\pi}{N} p_ic)$, $C\subseteq [N]$ is a
feasible set of solutions, and $\lambda$ is a given regularization function.
For any approximation error $\varepsilon>0$, we prove that \emph{every} set $P$
of $n$ integers has a weighted subset $S\subseteq P$ (sometimes called
core-set) of cardinality $|S|\in O(\log(N)^{O(1)})$ that approximates
$cost(P,c)$ (for every $c\in [N]$) up to a multiplicative factor of
$1\pm\varepsilon$. Using known coreset techniques, this implies streaming
algorithms using only $O((\log(N)\log(n))^{O(1)})$ memory. Our results hold for
a large family of functions. Experimental results and open source code are
provided.
- Abstract（参考訳）: emph{monitoring}問題では、入力は、センサー(gpsや人間の心拍数など)から得られる$[n]:=\{1,\cdots,n\}$の整数の無制限ストリーム$p={p_1,p_2\cdots}$である。
例えば、異常検出のためのゴールは、これまで$P$で受け取った$n$ポイントを単一の周波数$\sin$、例えば$\min_{c\in C} Cost(P,c)+\lambda(c)$、$cost(P,c)=\sum_{i=1}^n \sin^2(\frac{2\pi}{N} p_ic)$、$C\subseteq [N]$ で近似することであり、$\lambda$ は与えられた正規化関数である。
任意の近似誤差$\varepsilon>0$に対して、 \emph{every} set $p$ of $n$ integers が$|s|\in o(\log(n)^{o(1)})$ の重み付き部分集合 $s\subseteq p$(時々core-setと呼ばれる)を持つことが証明され、これは$cost(p,c)$(すべての$c\in [n]$) から$\pm\varepsilon$ の乗算係数まで近似する。
これは、既知のコアセット技術を用いて、$O((\log(N)\log(n))^{O(1)})$メモリを使用するストリーミングアルゴリズムを意味する。
我々の結果は大きな機能のファミリーを支えている。
実験結果とオープンソースコードが提供されている。
関連論文リスト
- Sharp Noisy Binary Search with Monotonic Probabilities [5.563988395126509]
我々はKarpとKleinbergのノイズの多いバイナリ検索モデルを再検討する。
我々は[ frac1C_tau, varepsilon cdot left(lg n + O(log2/3 n log 1/3 frac1delta + log frac1delta)右から1-delta$の確率で成功するアルゴリズムを作成する。
論文 参考訳（メタデータ） (2023-11-01T20:45:13Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
我々は、任意のSchatten-$p$ノルムの下で、低ランク近似のためのクリロフ部分空間に基づく反復法について研究する。
我々の主な成果は、$tildeO(k/sqrtepsilon)$ matrix-vector productのみを使用するアルゴリズムである。
論文 参考訳（メタデータ） (2022-02-10T16:10:41Z) - Learning low-degree functions from a logarithmic number of random
queries [77.34726150561087]
任意の整数 $ninmathbbN$, $din1,ldots,n$ および任意の $varepsilon,deltain(0,1)$ に対して、有界関数 $f:-1,1nto[-1,1]$ に対して、少なくとも$d$ の次数を学ぶことができる。
論文 参考訳（メタデータ） (2021-09-21T13:19:04Z) - Faster Rates of Differentially Private Stochastic Convex Optimization [7.93728520583825]
人口リスク関数がTysbakovノイズ条件(TNC)をパラメータ$theta>1$で満たす場合について検討した。
第2部では,人口リスク関数が強く凸する特殊な事例に着目した。
論文 参考訳（メタデータ） (2021-07-31T22:23:39Z) - Optimal Coreset for Gaussian Kernel Density Estimation [0.8376091455761259]
点集合 $Psubset mathbbRd$ が与えられたとき、$P$ の核密度推定は [ overlinemathcalG_P(x) = frac1left|Pright|sum_pin Pe-leftlVert x-p rightrVert2 ] for any $xinmathbbRd$ と定義される。
我々は、小さなサブセット$Q$ of $P を構築する方法を研究する。
論文 参考訳（メタデータ） (2020-07-15T22:58:50Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳（メタデータ） (2020-06-06T13:34:41Z) - Sets Clustering [25.358415142404752]
我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。
このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。
オープンソースコードと文書分類および施設位置の実験結果も提供される。
論文 参考訳（メタデータ） (2020-03-09T13:30:30Z) - On the Complexity of Minimizing Convex Finite Sums Without Using the
Indices of the Individual Functions [62.01594253618911]
有限和の有限ノイズ構造を利用して、大域オラクルモデルの下での一致する$O(n2)$-upper境界を導出する。
同様のアプローチを踏襲したSVRGの新規な適応法を提案し、これはオラクルと互換性があり、$tildeO(n2+nsqrtL/mu)log (1/epsilon)$と$O(nsqrtL/epsilon)$, for $mu>0$と$mu=0$の複雑さ境界を実現する。
論文 参考訳（メタデータ） (2020-02-09T03:39:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。