論文の概要: Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
- arxiv url: http://arxiv.org/abs/2004.07986v1
- Date: Thu, 16 Apr 2020 22:57:06 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-12 21:20:02.481115
- Title: Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss
- Title（参考訳）: 平均値$\ell_1$-Norm損失に対する平均列サブセット選択
- Authors: Zhao Song, David P. Woodruff, Peilin Zhong
- Abstract要約: 最悪の場合、行列に対する良いランク-$k$近似を得るには、任意に大きい$nOmega(1)$列数が必要であることが知られている。
最小かつ現実的な分布設定では、ほぼ線形な実行時間を持つ$(k/epsilon)$-approximationとpoly$(k/epsilon)+O(klog n)$ columnsが得られる。
これは、エントリワイズで$(k/epsilon)$-approximationを達成するための任意の種類の最初のアルゴリズムである
- 参考スコア（独自算出の注目度）: 76.02734481158458
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: We study the column subset selection problem with respect to the entrywise
$\ell_1$-norm loss. It is known that in the worst case, to obtain a good
rank-$k$ approximation to a matrix, one needs an arbitrarily large
$n^{\Omega(1)}$ number of columns to obtain a $(1+\epsilon)$-approximation to
the best entrywise $\ell_1$-norm low rank approximation of an $n \times n$
matrix. Nevertheless, we show that under certain minimal and realistic
distributional settings, it is possible to obtain a
$(1+\epsilon)$-approximation with a nearly linear running time and
poly$(k/\epsilon)+O(k\log n)$ columns. Namely, we show that if the input matrix
$A$ has the form $A = B + E$, where $B$ is an arbitrary rank-$k$ matrix, and
$E$ is a matrix with i.i.d. entries drawn from any distribution $\mu$ for which
the $(1+\gamma)$-th moment exists, for an arbitrarily small constant $\gamma >
0$, then it is possible to obtain a $(1+\epsilon)$-approximate column subset
selection to the entrywise $\ell_1$-norm in nearly linear time. Conversely we
show that if the first moment does not exist, then it is not possible to obtain
a $(1+\epsilon)$-approximate subset selection algorithm even if one chooses any
$n^{o(1)}$ columns. This is the first algorithm of any kind for achieving a
$(1+\epsilon)$-approximation for entrywise $\ell_1$-norm loss low rank
approximation.
- Abstract（参考訳）: 我々は、エントリワイズ $\ell_1$-norm 損失に関して列の部分集合選択問題を調べる。
最悪の場合、行列に対する良い階数-$k$近似を得るには、$n \times n$Matrix の最良のエントリーに対して$(1+\epsilon)$-approximation を得るために、任意の大きさの$n^{\Omega(1)}$列数が必要であることが知られている。
それでも、ある最小かつ現実的な分布設定の下では、ほぼ線形な実行時間とpoly$(k/\epsilon)+O(k\log n)$列を持つ$(1+\epsilon)$-approximationが得られる。
すなわち、入力行列 $A$ が $A = B + E$ の形を持つなら、$B$ は任意の階数-$k$ 行列であり、$E$ は任意の分布から引き出された入射を持つ行列であり、$(1+\gamma)$-th moment は任意の小さな定数 $\gamma > 0$ に対して$(1+\epsilon)$-approximate column subset selection to the entrywise $\ell_1$-norm をほぼ線形時間で得ることができる。
逆に、最初のモーメントが存在しない場合、任意の$n^{o(1)}$列を選択しても$(1+\epsilon)$-approximate subset selectionアルゴリズムを得ることはできない。
これは、エントリワイズ$\ell_1$-normロスローランク近似に対して(1+\epsilon)$近似を達成するための、任意の種類の最初のアルゴリズムである。
関連論文リスト
- LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions [54.54897832889028]
任意の$K$に対して、$n$とは独立に「普遍集合」$Uサブセット[n]$が存在し、任意の$Q$と任意の行$i$に対して、大きな注目スコアが$A_i,j$ in row $i$ of $A$は全て$jin U$を持つことを示す。
我々は、視覚変換器のスキームの利点を実証的に示し、トレーニング中に我々の普遍的なセットを使用する新しいモデルのトレーニング方法を示した。
論文 参考訳（メタデータ） (2024-10-07T19:47:13Z) - 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) - Optimal Embedding Dimension for Sparse Subspace Embeddings [4.042707434058959]
ランダム$mtimes n$ matrix $S$は、忘れられない部分空間埋め込み(OSE)である。
mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ is an oblivious subspace embedding with $epsilon = O_theta(1)$。
これを使用すれば、現在の行列乗算時間よりも早く適用できる$O(d)$埋め込み次元で、最初の難解な部分空間埋め込みを構築することができる。
論文 参考訳（メタデータ） (2023-11-17T18:01:58Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳（メタデータ） (2023-06-02T18:55:27Z) - Krylov Methods are (nearly) Optimal for Low-Rank Approximation [8.017116107657206]
任意のアルゴリズムが$Omegaleft(log(n)/varepsilon1/2right)$ matrix-vector productを必要とし、Krylov法で得られる上限値と正確に一致することを示す。
我々の下位境界はOpen Question 1WooWoo14で、Spectral LRAのアルゴリズムの進歩の欠如の証拠を提供している。
論文 参考訳（メタデータ） (2023-04-06T16:15:19Z) - 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) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳（メタデータ） (2021-05-17T16:40:48Z) - Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank
Approximation [0.0]
カラムサブセット選択をベースとした$ell_p$ローランク近似アルゴリズムで$tildeO(k)$カラムをサンプリングする。
我々は、カラム部分集合選択に基づく$ell_p$低階近似を1p2$で厳密な上限と下限を得るように、結果を拡張した。
論文 参考訳（メタデータ） (2020-07-20T17:50:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。