Fugu-MT 論文翻訳(概要): Guessing Efficiently for Constrained Subspace Approximation

論文の概要: Guessing Efficiently for Constrained Subspace Approximation

arxiv url: http://arxiv.org/abs/2504.20883v1
Date: Tue, 29 Apr 2025 15:56:48 GMT
ステータス: 翻訳完了
システム内更新日: 2025-05-02 19:15:54.97347
Title: Guessing Efficiently for Constrained Subspace Approximation
Title（参考訳）: 制約付き部分空間近似の効率的解法
Authors: Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu, Ali Vakilian, David P. Woodruff,
Abstract要約: 制約付き部分空間近似のための一般的なフレームワークを導入する。分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
参考スコア（独自算出の注目度）: 49.83981776254246
License: http://creativecommons.org/licenses/by/4.0/
Abstract: In this paper we study constrained subspace approximation problem. Given a set of $n$ points $\{a_1,\ldots,a_n\}$ in $\mathbb{R}^d$, the goal of the {\em subspace approximation} problem is to find a $k$ dimensional subspace that best approximates the input points. More precisely, for a given $p\geq 1$, we aim to minimize the $p$th power of the $\ell_p$ norm of the error vector $(\|a_1-\bm{P}a_1\|,\ldots,\|a_n-\bm{P}a_n\|)$, where $\bm{P}$ denotes the projection matrix onto the subspace and the norms are Euclidean. In \emph{constrained} subspace approximation (CSA), we additionally have constraints on the projection matrix $\bm{P}$. In its most general form, we require $\bm{P}$ to belong to a given subset $\mathcal{S}$ that is described explicitly or implicitly. We introduce a general framework for constrained subspace approximation. Our approach, that we term coreset-guess-solve, yields either $(1+\varepsilon)$-multiplicative or $\varepsilon$-additive approximations for a variety of constraints. We show that it provides new algorithms for partition-constrained subspace approximation with applications to {\it fair} subspace approximation, $k$-means clustering, and projected non-negative matrix factorization, among others. Specifically, while we reconstruct the best known bounds for $k$-means clustering in Euclidean spaces, we improve the known results for the remainder of the problems.
Abstract（参考訳）: 本稿では,制約付き部分空間近似問題について検討する。 1組の$n$ポイント $\{a_1,\ldots,a_n\}$ in $\mathbb{R}^d$ が与えられたとき、 {\em subspace approximation} 問題の目標は入力点を最もよく近似する$k$次元部分空間を見つけることである。より正確には、与えられた$p\geq 1$に対して、誤差ベクトル $(\|a_1-\bm{P}a_1\|,\ldots,\|a_n-\bm{P}a_n\|)$ の$\ell_p$ノルムの$p$のパワーを最小化することを目指している。 Emph{constrained} subspace approximation (CSA) では、射影行列 $\bm{P}$ にも制約がある。最も一般的な形式では、与えられた部分集合 $\mathcal{S}$ に属するために $\bm{P}$ を明示的にまたは暗黙的に記述する必要がある。制約付き部分空間近似のための一般的なフレームワークを導入する。我々がcoreset-guess-solveと呼ぶアプローチは、様々な制約に対して$(1+\varepsilon)$-multiplicativeまたは$\varepsilon$-additive approximationsをもたらす。分割制約付き部分空間近似の新しいアルゴリズムとして, 部分空間近似, $k$-meansクラスタリング, 非負行列分解などの応用を提案する。具体的には、ユークリッド空間における$k$-meansクラスタリングの最もよく知られた境界を再構築する一方で、残りの問題に対する既知の結果を改善する。

関連論文リスト

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity [3.9657575162895196]
曖昧な部分空間の埋め込みは、ランダムな$mtimes n$ matrix $Pi$で、その部分空間内のすべてのベクトルのノルムを1pmepsilon$ factorで保存する。最適次元が $m=Theta(d/epsilon2)$ で、最適間隔が $tilde O (1/epsilon)$ のとき、非零エントリは $Pi$ である。
論文参考訳（メタデータ） (2024-11-13T16:58:51Z)
The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
この問題は通信複雑性のランダム化を$Omega(frac1kcdot n2log|mathbbF|)$とする。アプリケーションとして、$k$パスを持つ任意のストリーミングアルゴリズムに対して、$Omega(frac1kcdot n2log|mathbbF|)$スペースローバウンドを得る。
論文参考訳（メタデータ） (2024-10-26T06:21:42Z)
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)
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)
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)
One-pass additive-error subset selection for $\ell_{p}$ subspace approximation [6.186553186139257]
我々は $ell_p$ 部分空間近似に対する部分集合選択の問題を考える。我々は、$ell_p$ subspace approximationの加算近似を保証した1パスのサブセット選択を与える。
論文参考訳（メタデータ） (2022-04-26T04:51:36Z)
Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文参考訳（メタデータ） (2022-04-13T22:18:47Z)
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)
Subspace approximation with outliers [6.186553186139257]
本稿では, オフリヤを用いた部分空間近似問題に対するサンプリングに基づいて, 次元削減手法と双基準近似を拡張する方法を示す。我々の結果は、0 delta leq 1 - α$ が満たされる条件が満たされる限り、alpha$ が大きければ成り立つ。
論文参考訳（メタデータ） (2020-06-30T07:22:33Z)

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

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