Fugu-MT 論文翻訳(概要): Nearly Linear Sparsification of $\ell

論文の概要: Nearly Linear Sparsification of $\ell_p$ Subspace Approximation

arxiv url: http://arxiv.org/abs/2407.03262v1
Date: Wed, 3 Jul 2024 16:49:28 GMT
ステータス: 処理完了
システム内更新日: 2024-07-04 13:17:22.538218
Title: Nearly Linear Sparsification of $\ell_p$ Subspace Approximation
Title（参考訳）: $\ell_p$ 部分空間近似のほぼ線形スカラー化
Authors: David P. Woodruff, Taisuke Yasuda,
Abstract要約: $ell_p$ 部分空間近似問題のNP硬度に対処する一般的なアプローチは、強いコアセットを計算することである。我々は、$ell_p$部分空間近似に対して、ランクパラメータ$k$にほぼ最適に依存する強いコアセットを構築するための最初のアルゴリズムを得る。我々の手法は、オフライン設定と同様のバウンダリを持つ$ell_p$サブスペース近似のための、ほぼ最適に近いオンライン強力なコアセットにも繋がる。
参考スコア（独自算出の注目度）: 47.790126028106734
License: http://creativecommons.org/licenses/by/4.0/
Abstract: The $\ell_p$ subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane problem ($p = 1$), principal component analysis ($p = 2$), and the center hyperplane problem ($p = \infty$). A popular approach to cope with the NP-hardness of this problem is to compute a strong coreset, which is a small weighted subset of the input points which simultaneously approximates the cost of every $k$-dimensional subspace, typically to $(1+\varepsilon)$ relative error for a small constant $\varepsilon$. We obtain the first algorithm for constructing a strong coreset for $\ell_p$ subspace approximation with a nearly optimal dependence on the rank parameter $k$, obtaining a nearly linear bound of $\tilde O(k)\mathrm{poly}(\varepsilon^{-1})$ for $p<2$ and $\tilde O(k^{p/2})\mathrm{poly}(\varepsilon^{-1})$ for $p>2$. Prior constructions either achieved a similar size bound but produced a coreset with a modification of the original points [SW18, FKW21], or produced a coreset of the original points but lost $\mathrm{poly}(k)$ factors in the coreset size [HV20, WY23]. 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)は、主成分解析(英: principal component analysis)(p = 2$)、中心超平面問題(英: center hyperplane problem)(p = \infty$)を一般化するNPハード低階近似問題である。この問題のNPハードネスに対処する一般的なアプローチは、入力点の小さな重み付き部分集合である強いコアセットを計算することであり、これは、通常、小さな定数$\varepsilon$に対して、$1+\varepsilon)$相対誤差に対して、すべての$k$-次元部分空間のコストを同時に近似するものである。 p<2$および$\tilde O(k^{p/2})\mathrm{poly}(\varepsilon^{-1})$ for $p>2$。以前の構成では、同じサイズ境界に達したが、原点の変更によるコアセットを作成した(SW18, FKW21] か、原点のコアセットを作成したが、コアセットサイズ [HV20, WY23] の$\mathrm{poly}(k)$因子を失った。我々の手法は、オフライン設定と同様のバウンダリを持つ$\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)

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

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