Fugu-MT 論文翻訳(概要): Optimal Matrix Sketching over Sliding Windows

論文の概要: Optimal Matrix Sketching over Sliding Windows

arxiv url: http://arxiv.org/abs/2405.07792v2
Date: Tue, 05 Nov 2024 11:58:50 GMT
ステータス: 翻訳完了
システム内更新日: 2024-11-06 14:55:07.597510
Title: Optimal Matrix Sketching over Sliding Windows
Title（参考訳）: スライディングウィンドウ上での最適マトリックススケッチ
Authors: Hanyan Yin, Dongxie Wen, Jiajun Li, Zhewei Wei, Xiao Zhang, Zengfeng Huang, Feifei Li,
Abstract要約: マトリックススケッチは、mathbbRNtimes d$で行列 $boldsymbolAを近似することを目的としており、長さ$N$のベクトルストリームとmathbbRelltimes d, ell ll N$で小さなスケッチマトリックス $boldsymbolBで構成されている。 Oleftfracdvarepsilonright)$ space bound for matrix sketching over row-normalized, sequence-based sliding windows。
参考スコア（独自算出の注目度）: 38.09464189820894
License:
Abstract: Matrix sketching, aimed at approximating a matrix $\boldsymbol{A} \in \mathbb{R}^{N\times d}$ consisting of vector streams of length $N$ with a smaller sketching matrix $\boldsymbol{B} \in \mathbb{R}^{\ell\times d}, \ell \ll N$, has garnered increasing attention in fields such as large-scale data analytics and machine learning. A well-known deterministic matrix sketching method is the Frequent Directions algorithm, which achieves the optimal $O\left(\frac{d}{\varepsilon}\right)$ space bound and provides a covariance error guarantee of $\varepsilon = \lVert \boldsymbol{A}^\top \boldsymbol{A} - \boldsymbol{B}^\top \boldsymbol{B} \rVert_2/\lVert \boldsymbol{A} \rVert_F^2$. The matrix sketching problem becomes particularly interesting in the context of sliding windows, where the goal is to approximate the matrix $\boldsymbol{A}_W$, formed by input vectors over the most recent $N$ time units. However, despite recent efforts, whether achieving the optimal $O\left(\frac{d}{\varepsilon}\right)$ space bound on sliding windows is possible has remained an open question. In this paper, we introduce the DS-FD algorithm, which achieves the optimal $O\left(\frac{d}{\varepsilon}\right)$ space bound for matrix sketching over row-normalized, sequence-based sliding windows. We also present matching upper and lower space bounds for time-based and unnormalized sliding windows, demonstrating the generality and optimality of \dsfd across various sliding window models. This conclusively answers the open question regarding the optimal space bound for matrix sketching over sliding windows. Furthermore, we conduct extensive experiments with both synthetic and real-world datasets, validating our theoretical claims and thus confirming the correctness and effectiveness of our algorithm, both theoretically and empirically.
Abstract（参考訳）: 行列スケッチは、行列 $\boldsymbol{A} \in \mathbb{R}^{N\times d}$ のベクトルストリームからなる行列 $N$ と小さなスケッチ行列 $\boldsymbol{B} \in \mathbb{R}^{\ell\times d}, \ell \ll N$ を近似することを目的としており、大規模データ分析や機械学習などの分野における注目を集めている。良く知られた決定論的行列スケッチ法は、Frequent Directionsアルゴリズムであり、最適$O\left(\frac{d}{\varepsilon}\right)$ spaceboundを達成し、$\varepsilon = \lVert \boldsymbol{A}^\top \boldsymbol{A} - \boldsymbol{B}^\top \boldsymbol{B} \rVert_2/\lVert \boldsymbol{A} \rVert_F^2$$の共分散誤差保証を提供する。行列スケッチ問題は、直近の$N$時間単位上の入力ベクトルによって形成される行列 $\boldsymbol{A}_W$ を近似することを目標とするスライディングウィンドウの文脈で特に興味深いものとなる。しかし、最近の試みにもかかわらず、スライドウィンドウ上の最適な$O\left(\frac{d}{\varepsilon}\right)$空間を達成できるかどうかは未解決のままである。本稿では,行正規化されたシーケンスベースのスライディングウィンドウ上での行列スケッチに最適な$O\left(\frac{d}{\varepsilon}\right)$スペースバウンドを実現するDS-FDアルゴリズムを提案する。また、時間ベースおよび非正規化されたスライディングウインドウに対して、上と下の境界をマッチングし、様々なスライディングウインドウモデルにおける \dsfd の一般化と最適性を示す。このことは、スライドウィンドウ上の行列スケッチのための最適空間に関するオープンな疑問に決定的に答える。さらに、我々は、合成と実世界の両方のデータセットで広範な実験を行い、理論的クレームを検証し、理論的にも経験的にも、アルゴリズムの正しさと有効性を確認する。

論文の概要: Optimal Matrix Sketching over Sliding Windows

関連論文リスト