論文の概要: Terminal Dimension Reduction for Time Series with Applications
- arxiv url: http://arxiv.org/abs/2607.09490v1
- Date: Fri, 10 Jul 2026 15:05:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-13 14:47:12.878617
- Title: Terminal Dimension Reduction for Time Series with Applications
- Title（参考訳）: 時系列の終端次元削減と応用
- Abstract要約: ターミナル埋め込みは次元減少のための強力なツールとして登場した。
この問題を克服するアフィン線分への終端埋め込みの一般化を開発する。
フレシェ距離の下で時系列をクラスタリングするための最初の次元自由コアセットを得る。
- 参考スコア（独自算出の注目度）: 53.49083917849734
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Terminal embeddings have emerged as a powerful tool for dimension reduction. Given a set of points $P\subset \mathbb{R}^d$, a terminal embedding is a mapping $f:\mathbb{R}^d\rightarrow \mathbb{R}^t$ that preserves the pairwise distance between any pair of points $p\in P$ and $q\in \mathbb{R}^d$ up to small distortion under this mapping. Terminal embeddings have been particularly fruitful for constructing $k$-means and $k$-median coresets, where the objective is to find a typically weighted subset $Ω$ of $P$ such that for any candidate solution, the cost of the clustering objective on $Ω$ approximates the cost of the clustering objective on $P$ up to small distortion. Unfortunately, these techniques have not been extended to more complicated structures such as clustering time-series data under common straight-line interpolation between measurements. The main issue is that terminal embeddings, arguably the central technique in this line of research, cannot be linear and are thus not immediately suitable to preserve linear structures. In this work, we develop a generalization of terminal embeddings to affine line-segments that overcomes this issue. We showcase their applicability by using our lines-preserving terminal embeddings to obtain the first dimension-free coresets for clustering time-series under the Fréchet distance. The underlying dimension reduction uses Johnson-Lindenstrauss (JL) embeddings, and our experiments indicate that terminal embeddings perform similarly to JL and favorably against PCA for synthetic and real-world time-series, while only terminal embeddings extend pairwise distance preservation to the full ambient space.
- Abstract（参考訳）: ターミナル埋め込みは次元減少のための強力なツールとして登場した。
点の集合 P\subset \mathbb{R}^d$ が与えられたとき、端末埋め込みは写像 $f:\mathbb{R}^d\rightarrow \mathbb{R}^t$ であり、任意の点の対である $p\in P$ と $q\in \mathbb{R}^d$ の間の対距離を保存する。
ターミナル埋め込みは、$k$-means と $k$-median のコアセットを構築するのに特に有益である。そこでの目的は、一般に重み付けされたサブセット $Ω$ of $P$ を見つけることである。
残念ながら、これらの手法は、測定間の共通の直線補間の下でのクラスタリング時系列データのような、より複雑な構造にまで拡張されていない。
主な問題は、この研究において中心となる技術である端末の埋め込みが線形でないことであり、したがって、線形構造を維持するのにすぐには適さないことである。
本研究では,この問題を克服するアフィン線分への終端埋め込みの一般化を開発する。
Fréchet 距離で時系列をクラスタリングするための最初の次元自由コアセットを得るために, 線形保存端子埋め込みを用いて, それらの適用性を示す。
基礎となる次元の縮小はジョンソン・リンデンシュトラウス (JL) の埋め込みを用いており, 実験により, 終端埋め込みはJLと類似し, 合成および実世界の時系列のPCAに対して良好に作用し, 終端埋め込みのみが全周囲空間への対方向距離保存を延長することを示した。
関連論文リスト
- Dimension Reduction for Curves: Simplified and Generalized [56.23281156053955]
我々は高次元多角曲線の次元を減少させるためにランダムな射影を再考する。
我々は、既知の$O(varepsilon-2log(nm))$がランダム射影のターゲット次元に有界であることの簡単な証明を与える。
我々の証明はスパース・オブリビラスな部分空間埋め込みの概念に基づいている。
論文 参考訳（メタデータ） (2026-07-03T08:48:35Z) - FlatVPR: Plug-and-play Geo-linear Residual Adapter for Geometric Rectification of Foundation Model Feature Manifolds [0.7734726150561086]
FlatVPR'は、視覚的位置認識における地図軽量性と位置決め精度のトレードオフを橋渡しする。
本手法は, 数学的に接地したプルバック平坦性損失を用いて, 多様体曲率を明示的に抑制する。
NCLTデータセットの実験では、アダプタの適用によってパフォーマンスが大幅に向上することを示した。
論文 参考訳（メタデータ） (2026-06-01T05:56:59Z) - Intrinsic Wasserstein Rates for Score-Based Generative Models on Smooth Manifolds [61.14405512940818]
Scoreベースの生成モデルは高次元空間で訓練されていることを示す。
有限固有アンカーとガウス・ニュートンによる最も近い射影座標のReLU実装を用いる。
論文 参考訳（メタデータ） (2026-05-15T10:20:05Z) - Low-degree Lower bounds for clustering in moderate dimension [53.03724383992195]
我々は、$n$点を$K$群にクラスタリングする根本的な問題を、$mathbbRd$における等方ガウスの混合から引き出された。
我々は、$n leq dK$のクラスタリングの難しさは次元の縮小とスペクトル法によって引き起こされるが、中等次元のレジームはより微妙な現象を伴い、「非最適率」につながることを示した。
我々は、この速度にマッチする新しい非スペクトルアルゴリズムを提案し、中等次元のクラスタリング問題の計算限界に新しい光を当てる。
論文 参考訳（メタデータ） (2026-02-26T14:03:55Z) - Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
制約付き部分空間近似のための一般的なフレームワークを導入する。
分割制約付き部分空間近似のための新しいアルゴリズムを$k$-meansクラスタリングに適用し、非負行列分解を投影する。
論文 参考訳（メタデータ） (2025-04-29T15:56:48Z) - Metric Embeddings Beyond Bi-Lipschitz Distortion via Sherali-Adams [34.7582575446942]
準多項式依存のMDSに対する最初の近似アルゴリズムをDeltaに与える。
本アルゴリズムは,シェラリ・アダムスLPの条件付きラウンドリングの幾何学的認識に基づく新しい解析法である。
論文 参考訳（メタデータ） (2023-11-29T17:42:05Z) - Parameterized Approximation Schemes for Clustering with General Norm
Objectives [0.6956677722498498]
本稿では、$(k,epsilon)$-approximationアルゴリズムを$k$-clustering問題に対して設計する、よく研究されている方式について考察する。
私たちの主な貢献は、クリーンでシンプルなEPASで、10以上のクラスタリング問題を解決しています。
論文 参考訳（メタデータ） (2023-04-06T15:31:37Z) - Generalization Bounds for Stochastic Gradient Descent via Localized
$\varepsilon$-Covers [16.618918548497223]
本稿では,SGDの軌道に局在する新しい被覆手法を提案する。
このローカライゼーションは、境界数によって測定されるアルゴリズム固有のクラスタリングを提供する。
これらの結果は様々な文脈で導き出され、既知の最先端のラベルレートが向上する。
論文 参考訳（メタデータ） (2022-09-19T12:11:07Z) - A Law of Robustness beyond Isoperimetry [84.33752026418045]
我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。
次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。
我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
論文 参考訳（メタデータ） (2022-02-23T16:10:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。