論文の概要: 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)$近似を達成するための、任意の種類の最初のアルゴリズムである。
関連論文リスト
- Optimal Embedding Dimension for Sparse Subspace Embeddings [13.387361384552484]
ランダム$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) - Hardness of Low Rank Approximation of Entrywise Transformed Matrix
Products [9.661328973620531]
自然言語処理における高速アルゴリズムにインスパイアされ、エントリ変換された設定における低階近似について研究する。
我々は、平坦なスパースベクトルのレバレッジスコアの低境界に依存するStrong Exponential Time hypothesis (SETH) から、新しい還元を与える。
我々の低階アルゴリズムは行列ベクトルに依存しているため、我々の下限は、小さな行列に対してさえも$f(UV)W$は$Omega(n2-o(1))$時間を必要とすることを示すために拡張される。
論文 参考訳(メタデータ) (2023-11-03T14:56:24Z) - 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) - Spectral properties of sample covariance matrices arising from random
matrices with independent non identically distributed columns [50.053491972003656]
関数 $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$.
ここでは、$|mathbb E[R(z)] - tilde R(z)|_F を示す。
論文 参考訳(メタデータ) (2021-09-06T14:21:43Z) - 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) - The Average-Case Time Complexity of Certifying the Restricted Isometry
Property [66.65353643599899]
圧縮センシングにおいて、100万倍のN$センシング行列上の制限等尺性(RIP)はスパースベクトルの効率的な再構成を保証する。
Mtimes N$ matrices with i.d.$mathcalN(0,1/M)$ entry。
論文 参考訳(メタデータ) (2020-05-22T16:55:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。