論文の概要: Quantum (Inspired) $D^2$-sampling with Applications

• arxiv url: http://arxiv.org/abs/2405.13351v1
• Date: Wed, 22 May 2024 05:13:28 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-25 01:24:25.577131
• Title: Quantum (Inspired) $D^2$-sampling with Applications
• Title（参考訳）: 量子(インスパイアされた)$D^2$-sampling with Applications
• Authors: Ragesh Jaiswal, Poojan Shah,
• Abstract要約: 我々は、$k$-means++の量子実装を示し、その時間は$tildeO(zeta2 k2)$で実行される。 これは、量子バージョンが$O(logk)$近似を保証する$k$-means++の堅牢な近似解析によって示される。 これはQI-$k$-means++と呼ばれ、実行時間は$O(Nd) + tildeO(zeta)である。
• 参考スコア（独自算出の注目度）: 0.138120109831448
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: $D^2$-sampling is a fundamental component of sampling-based clustering algorithms such as $k$-means++. Given a dataset $V \subset \mathbb{R}^d$ with $N$ points and a center set $C \subset \mathbb{R}^d$, $D^2$-sampling refers to picking a point from $V$ where the sampling probability of a point is proportional to its squared distance from the nearest center in $C$. Starting with empty $C$ and iteratively $D^2$-sampling and updating $C$ in $k$ rounds is precisely $k$-means++ seeding that runs in $O(Nkd)$ time and gives $O(\log{k})$-approximation in expectation for the $k$-means problem. We give a quantum algorithm for (approximate) $D^2$-sampling in the QRAM model that results in a quantum implementation of $k$-means++ that runs in time $\tilde{O}(\zeta^2 k^2)$. Here $\zeta$ is the aspect ratio (i.e., largest to smallest interpoint distance), and $\tilde{O}$ hides polylogarithmic factors in $N, d, k$. It can be shown through a robust approximation analysis of $k$-means++ that the quantum version preserves its $O(\log{k})$ approximation guarantee. Further, we show that our quantum algorithm for $D^2$-sampling can be 'dequantized' using the sample-query access model of Tang (PhD Thesis, Ewin Tang, University of Washington, 2023). This results in a fast quantum-inspired classical implementation of $k$-means++, which we call QI-$k$-means++, with a running time $O(Nd) + \tilde{O}(\zeta^2k^2d)$, where the $O(Nd)$ term is for setting up the sample-query access data structure. Experimental investigations show promising results for QI-$k$-means++ on large datasets with bounded aspect ratio. Finally, we use our quantum $D^2$-sampling with the known $ D^2$-sampling-based classical approximation scheme (i.e., $(1+\varepsilon)$-approximation for any given $\varepsilon>0$) to obtain the first quantum approximation scheme for the $k$-means problem with polylogarithmic running time dependence on $N$.
• Abstract（参考訳）: $D^2$-samplingは、$k$-means++のようなサンプリングベースのクラスタリングアルゴリズムの基本コンポーネントである。 データセット $V \subset \mathbb{R}^d$ に$N$ポイントとセンターセット $C \subset \mathbb{R}^d$ が与えられたとき、$D^2$-sampling は、ある点のサンプリング確率が$C$の最も近い中心から2乗距離に比例する$V$から点を選ぶことを指す。 空の$C$から始まり、反復的に$D^2$-samplingし、$k$のラウンドで$C$を更新すると、正確に$k$-means++シードで、$O(Nkd)$ timeで実行され、$k$-means問題に期待して$O(\log{k})$-approximationを与える。 QRAMモデルにおける(近似的な)$D^2$-samplingの量子アルゴリズムを与え、その結果、$k$-means++の量子実装が、時間で$\tilde{O}(\zeta^2 k^2)$で実行される。 ここで、$\zeta$はアスペクト比(すなわち、最大から最小のインターポイント距離)であり、$\tilde{O}$はポリ対数因子を$N, d, k$に隠す。 これは、量子バージョンが$O(\log{k})$近似を保証する$k$-means++の堅牢な近似解析によって示される。 さらに,Tang(PhD Thesis, Ewin Tang, University of Washington, 2023)のサンプルクエリアクセスモデルを用いて,D^2$-samplingの量子アルゴリズムを'復号化'できることを示す。 これはQI-$k$-means++と呼ばれ、実行時間$O(Nd) + \tilde{O}(\zeta^2k^2d)$である。 実験により,境界アスペクト比を持つ大規模データセット上でのQI-$k$-means++の有望な結果が示された。 最後に、既知の$D^2$-sampling-based classical approximation scheme(例えば$(1+\varepsilon)$-approximation for any given $\varepsilon>0$)を用いて、$k$-means問題に対する最初の量子近似スキームを得る。

関連論文リスト

• Measuring quantum relative entropy with finite-size effect [53.64687146666141]
  相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。 我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
  論文  参考訳（メタデータ） (2024-06-25T06:07:20Z)
• Do you know what q-means? [50.045011844765185]
  クラスタリングは、大規模なデータセットを分析する上で最も重要なツールの1つである。 クラスタリングのための"$q$-means"アルゴリズムの改良版を提案する。 また、$Obig(frack2varepsilon2(sqrtkd + log(Nd))big で実行される $varepsilon に対する "dequantized" アルゴリズムも提示する。
  論文  参考訳（メタデータ） (2023-08-18T17:52:12Z)
• A Quantum Approximation Scheme for k-Means [0.16317061277457]
  QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。 我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。 教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
  論文  参考訳（メタデータ） (2023-08-16T06:46:37Z)
• Efficient Sampling of Stochastic Differential Equations with Positive Semi-Definite Models [91.22420505636006]
  本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。 1/varepsilonは$m2d log (1/varepsilon)$である。 以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
  論文  参考訳（メタデータ） (2023-03-30T02:50:49Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Improved quantum data analysis [1.8416014644193066]
  我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。 また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
  論文  参考訳（メタデータ） (2020-11-22T01:22:37Z)
• Denoising modulo samples: k-NN regression and tightness of SDP relaxation [5.025654873456756]
  サンプルの値が$f(x_i)$で一様誤差率$O(fraclog nn)frac1d+2)$を高い確率で保持する2段階のアルゴリズムを導出する。 サンプル $f(x_i)$ の見積もりは、その後、関数 $f$ の見積もりを構築するために使われる。
  論文  参考訳（メタデータ） (2020-09-10T13:32:46Z)
• The Quantum Supremacy Tsirelson Inequality [0.22843885788439797]
  量子回路 $C$ on $n$ qubits とサンプル $z in 0,1n$ のとき、ベンチマークは$|langle z|C|0n rangle|2$ の計算を伴う。 任意の $varepsilon ge frac1mathrmpoly(n)$ に対して、サンプル $z$ を出力することは、平均で $|langle z|C|0nrangle|2$ に対して最適な 1-クエリであることを示す。
  論文  参考訳（メタデータ） (2020-08-20T01:04:32Z)
• Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
  学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。 i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
  論文  参考訳（メタデータ） (2020-07-16T06:44:44Z)
• Streaming Complexity of SVMs [110.63976030971106]
  本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。 両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
  論文  参考訳（メタデータ） (2020-07-07T17:10:00Z)

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

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