論文の概要: Deterministic Coreset for Lp Subspace

• arxiv url: http://arxiv.org/abs/2601.00361v1
• Date: Thu, 01 Jan 2026 14:31:16 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-05 15:04:33.400891
• Title: Deterministic Coreset for Lp Subspace
• Title（参考訳）: Lp部分空間に対する決定論的コアセット
• Authors: Rachit Chhaya, Anirban Dasgupta, Dan Feldman, Supratim Shit,
• Abstract要約: 本稿では,決定論的$ell_p$サブスペース埋め込みを保証する$varepsilon$-coresetを構築するための最初の反復アルゴリズムを紹介する。 各イテレーションにおいて、アルゴリズムは、保守されたセットの損失が元のデータセットの損失によって上と下の境界であることを保証する。 我々のコアセットは $ell_p$ 回帰問題を決定論的に解くのにも使える。
• 参考スコア（独自算出の注目度）: 10.070877057133004
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce the first iterative algorithm for constructing a $\varepsilon$-coreset that guarantees deterministic $\ell_p$ subspace embedding for any $p \in [1,\infty)$ and any $\varepsilon > 0$. For a given full rank matrix $\mathbf{X} \in \mathbb{R}^{n \times d}$ where $n \gg d$, $\mathbf{X}' \in \mathbb{R}^{m \times d}$ is an $(\varepsilon,\ell_p)$-subspace embedding of $\mathbf{X}$, if for every $\mathbf{q} \in \mathbb{R}^d$, $(1-\varepsilon)\|\mathbf{Xq}\|_{p}^{p} \leq \|\mathbf{X'q}\|_{p}^{p} \leq (1+\varepsilon)\|\mathbf{Xq}\|_{p}^{p}$. Specifically, in this paper, $\mathbf{X}'$ is a weighted subset of rows of $\mathbf{X}$ which is commonly known in the literature as a coreset. In every iteration, the algorithm ensures that the loss on the maintained set is upper and lower bounded by the loss on the original dataset with appropriate scalings. So, unlike typical coreset guarantees, due to bounded loss, our coreset gives a deterministic guarantee for the $\ell_p$ subspace embedding. For an error parameter $\varepsilon$, our algorithm takes $O(\mathrm{poly}(n,d,\varepsilon^{-1}))$ time and returns a deterministic $\varepsilon$-coreset, for $\ell_p$ subspace embedding whose size is $O\left(\frac{d^{\max\{1,p/2\}}}{\varepsilon^{2}}\right)$. Here, we remove the $\log$ factors in the coreset size, which had been a long-standing open problem. Our coresets are optimal as they are tight with the lower bound. As an application, our coreset can also be used for approximately solving the $\ell_p$ regression problem in a deterministic manner.
• Abstract（参考訳）: 決定論的$\ell_p$サブスペース埋め込みを保証する$\varepsilon$-coresetと、任意の$p \in [1,\infty)$および任意の$\varepsilon > 0$を構築するための最初の反復アルゴリズムを導入する。 与えられたフルランク行列に対して、$\mathbf{X} \in \mathbb{R}^{n \times d}$ where $n \gg d$, $\mathbf{X}' \in \mathbb{R}^{m \times d}$ is a $(\varepsilon,\ell_p)$-subspace embedding of $\mathbf{X}$, if for every $\mathbf{q} \in \mathbb{R}^d$, $(1-\varepsilon)\|\mathbf{Xq}\|_{p}^{p} \leq \|\mathbf{X'q}\|_{p}^{p} \leq (1+\varepsilon)\|\mathbf{X}|_{p}^{p} \leq (1+\varepsilon)\|\mathbf{X'q}\|_{p}^{p} である。 具体的には、$\mathbf{X}'$ は $\mathbf{X}$ の行の重み付き部分集合である。 各イテレーションにおいて、アルゴリズムは、保守されたセットの損失が、適切なスケーリングで元のデータセットの損失によって上下に制限されていることを保証します。 したがって、通常のコアセットの保証とは異なり、バウンドロスのため、コアセットは$\ell_p$サブスペースの埋め込みを決定論的に保証する。 エラーパラメータ $\varepsilon$ に対して、我々のアルゴリズムは $O(\mathrm{poly}(n,d,\varepsilon^{-1}))$ time を取り、決定論的 $\varepsilon$-coreset を返す。 ここでは、長年の未解決問題であったコアセットサイズの$\log$要素を取り除きます。 私たちのコアセットは、低い境界に密着しているため、最適です。 アプリケーションとして、我々のコアセットは、決定論的手法で$\ell_p$レグレッション問題を解くのに使える。

関連論文リスト

• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  制約付き部分空間近似のための一般的なフレームワークを導入する。 分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
  論文  参考訳（メタデータ） (2025-04-29T15:56:48Z)
• Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation [47.790126028106734]
  NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。 我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-07-03T16:49:28Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。 1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
  論文  参考訳（メタデータ） (2024-06-04T15:50:42Z)
• Dimension-Independent Kernel ε-Covers [8.234735564035567]
  カーネル範囲空間は、X の部分集合 mathbbRd$ の集合と、固定されたカーネルによる全てのクエリの空間に関する。 カーネルレンジ空間に対して$varepsilon$-coverという概念を導入する。
  論文  参考訳（メタデータ） (2023-06-28T19:19:33Z)
• Improved Coresets for Euclidean $k$-Means [24.850829728643923]
  1組の$d$次元の$n$ポイントが与えられたとき、ユークリッド$k$平均問題(ユークリッド$k$中間問題を参照)は、$k$センターを見つけることからなる。 本稿では,$tilde O(min(k2 cdot varepsilon-2,kcdot varepsilon-4)$ for $k$-means and $tilde O(min(k4/3 cdot varepsilon)を改善する。
  論文  参考訳（メタデータ） (2022-11-15T14:47:24Z)
• 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)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。 この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
  論文  参考訳（メタデータ） (2021-08-19T16:16:48Z)
• Approximate Maximum Halfspace Discrepancy [6.35821487778241]
  範囲空間 $(X, MathcalH_d)$ ここで、$X の部分集合 mathbbRd$ と $mathcalH_d$ は、$d$ハーフスペースで定義される範囲の集合である。 数学 H_d$ における各半空間 $h に対して、$Phi(h)$ は、赤の分数と青の点の分数の差を測る関数 $Phi(h)$ を定義する。
  論文  参考訳（メタデータ） (2021-06-25T19:14:45Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)

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

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