論文の概要: Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation

• arxiv url: http://arxiv.org/abs/2407.03262v3
• Date: Thu, 03 Apr 2025 02:14:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-04-04 12:53:26.532526
• Title: Ridge Leverage Score Sampling for $\ell_p$ Subspace Approximation
• Title（参考訳）: Ridge Leverage Score Smpling for $\ell_p$ Subspace Approximation
• Authors: David P. Woodruff, Taisuke Yasuda,
• Abstract要約: NPハードネスに対処するための一般的なアプローチは、強力なコアセットを計算することである。 我々は$ell_p$サブスペース近似を$tilde O(kepsilon-4/p)$ for $p2$と$tilde O(kp/2epsilon-p)$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 47.790126028106734
• License:
• Abstract: The $\ell_p$ subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane ($p = 1$), principal component analysis ($p = 2$), and center hyperplane problems ($p = \infty$). A popular approach to cope with the NP-hardness is to compute a strong coreset, which is a weighted subset of input points that simultaneously approximates the cost of every $k$-dimensional subspace, typically to $(1+\epsilon)$ relative error for a small constant $\epsilon$. We obtain an algorithm for constructing a strong coreset for $\ell_p$ subspace approximation of size $\tilde O(k\epsilon^{-4/p})$ for $p<2$ and $\tilde O(k^{p/2}\epsilon^{-p})$ for $p>2$. This offers the following improvements over prior work: - We construct the first strong coresets with nearly optimal dependence on $k$ for all $p\neq 2$. In prior work, [SW18] constructed coresets of modified points with a similar dependence on $k$, while [HV20] constructed true coresets with polynomially worse dependence on $k$. - We recover or improve the best known $\epsilon$ dependence for all $p$. In particular, for $p > 2$, the [SW18] coreset of modified points had a dependence of $\epsilon^{-p^2/2}$ and the [HV20] coreset had a dependence of $\epsilon^{-3p}$. Our algorithm is based on sampling by root ridge leverage scores, which admits fast algorithms, especially for sparse or structured matrices. Our analysis avoids the use of the representative subspace theorem [SW18], which is a critical component of all prior dimension-independent coresets for $\ell_p$ subspace approximation. Our techniques also lead to the first nearly optimal online strong coresets for $\ell_p$ subspace approximation with similar bounds as the offline setting, resolving a problem of [WY23]. All prior approaches lose $\mathrm{poly}(k)$ factors in this setting, even when allowed to modify the original points.
• Abstract（参考訳）: $\ell_p$ 部分空間近似問題(英: $\ell_p$ subspace approximation problem)は、中心超平面(p = 1$)、主成分分析(p = 2$)、中心超平面問題(p = \infty$)を一般化するNPハード低階近似問題である。 NPハードネスに対処するための一般的なアプローチは、強いコアセットを計算することであり、これは入力点の重み付けされた部分集合であり、これは、通常、小さな定数$\epsilon$に対して1+\epsilon)$相対誤差の1+\epsilon$に、すべての$k$次元部分空間のコストを同時に近似する。 我々は、$\tilde O(k\epsilon^{-4/p})$ for $p<2$ and $\tilde O(k^{p/2}\epsilon^{-p})$ for $p>2$に対して強コアセットを構築するアルゴリズムを得る。 私たちは、すべての$p\neq 2$に対して$k$にほぼ最適な依存で、最初の強力なコアセットを構築します。 以前の作業では、[SW18]は$k$に類似した依存を持つ修正点のコアセットを構築し、[HV20]は$k$に多項式的に悪い依存を持つ真のコアセットを構築した。 -すべての$p$に対する最もよく知られている$\epsilon$依存を回復または改善します。 特に$p > 2$の場合、修正点の[SW18]コアセットは$\epsilon^{-p^2/2}$、[HV20]コアセットは$\epsilon^{-3p}$である。 我々のアルゴリズムは、特にスパース行列や構造化行列において高速なアルゴリズムを許容するルートリッジレバレッジスコアのサンプリングに基づいている。 我々の分析は、$\ell_p$ 部分空間近似に対するすべての先行次元非依存コアセットの臨界成分である代表部分空間定理 [SW18] の使用を避ける。 我々の手法は、オフライン設定と同様のバウンダリを持つ$\ell_p$サブスペース近似に対して、最初のほぼ最適のオンライン強コアセットをもたらし、[WY23]の問題を解決する。 以前のすべてのアプローチは、元の点を変更することを許されたとしても、この設定で$\mathrm{poly}(k)$因子を失う。

関連論文リスト

• Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
  線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。 これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。 また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
  論文  参考訳（メタデータ） (2024-08-16T02:33:07Z)
• Efficient Continual Finite-Sum Minimization [52.5238287567572]
  連続有限サム最小化(continuous finite-sum minimization)と呼ばれる有限サム最小化の鍵となるツイストを提案する。 我々のアプローチは$mathcalO(n/epsilon)$ FOs that $mathrmStochasticGradientDescent$で大幅に改善されます。 また、$mathcalOleft(n/epsilonalpharight)$ complexity gradient for $alpha 1/4$という自然な一階法は存在しないことを証明し、この方法の第一階法がほぼ密であることを示す。
  論文  参考訳（メタデータ） (2024-06-07T08:26:31Z)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。 また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
  論文  参考訳（メタデータ） (2023-05-12T08:43:28Z)
• 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)
• Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
  リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。 また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
  論文  参考訳（メタデータ） (2022-04-13T22:18:47Z)
• Towards Optimal Lower Bounds for k-median and k-means Coresets [25.713987341159918]
  計量空間における点の集合が与えられたとき、$(k,z)$-クラスタリング問題は、センターと呼ばれる点の集合を見つけることからなる。 我々は、$(k,z)$クラスタリングの任意のコアセットが、少なくとも$Omega(k varepsilon-2 log n)$と$Omega(k varepsilon-2 D)$ポイントでなければならないことを示す。
  論文  参考訳（メタデータ） (2022-02-25T16:13:28Z)
• Active Sampling for Linear Regression Beyond the $\ell_2$ Norm [70.49273459706546]
  対象ベクトルの少数のエントリのみを問合せすることを目的とした線形回帰のためのアクティブサンプリングアルゴリズムについて検討する。 我々はこの$d$への依存が対数的要因まで最適であることを示す。 また、損失関数に対して最初の全感度上界$O(dmax1,p/2log2 n)$を提供し、最大で$p$成長する。
  論文  参考訳（メタデータ） (2021-11-09T00:20:01Z)
• Subspace approximation with outliers [6.186553186139257]
  本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。 我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
  論文  参考訳（メタデータ） (2020-06-30T07:22:33Z)
• Sets Clustering [25.358415142404752]
  我々は、$O(logn)$集合のコア集合が常に存在することを証明し、$O(nlogn)$ timeで計算することができる。 このコアセットに非効率だが最適なアルゴリズムを適用することで、集合-k$-means問題に対する最初のPTAS(1+varepsilon$ approximation)を得ることができる。 オープンソースコードと文書分類および施設位置の実験結果も提供される。
  論文  参考訳（メタデータ） (2020-03-09T13:30:30Z)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。 我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
  論文  参考訳（メタデータ） (2020-02-12T03:40:52Z)

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

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