概要 - 非正規化ユークリッド距離のための$k$-PCA: 多項式時間近似

タイトル
非正規化ユークリッド距離のための$k$-PCA: 多項式時間近似

時間
2025-07-19 14:00:50

著者
{"Daniel Greenhut","Dan Feldman"}

カテゴリ
{cs.LG,cs.CG,cs.DS}

リンク
http://arxiv.org/abs/2507.14631v1

PDF リンク
http://arxiv.org/pdf/2507.14631v1

概要

この論文では、点とそれらに対応するk次元 subspace間の非平方ユークリッド距離の和を最小化することを目指す新しいアルゴリズム、kSM-Approxを提案しています。このアルゴリズムは、入力空間の次元数dを持つ乗法近似因子で確率的ポリノミアル時間解決を提供します。 kSM問題は、非凸性と効率的なアルゴリズムの欠如のため挑戦的です。既存の方法は、多くの場合、ランダムなアプローチに依存し、指数時間複雑度を持っています。提案されたアルゴリズムは、凸弛緩技術と中心経路法を用いてこれらの課題を解決します。 以下に、主要な貢献と発見の概要を示します： **アルゴリズムの概要**： 1. **弛緩**：kSM問題は、元の問題の凸弛緩である混合半定規制プログラミング（SDP）-二階球面規制プログラミング（SOCP）問題に弛緩されます。 2. **最適化**：弛緩された問題は、中心経路法を使用して解決され、最適解に対する加法的ε-近似を保証します。 3. **投影**：弛緩された問題の最適解は、元のkSM問題の適切な集合に投影され、kSMに対するd-近似を得ます。 **正しさの証明**： アルゴリズムの正しさは、投影された解が入力点に対する非平方ユークリッド距離の和を最小化し、最適kSMに対するdの係数で収束することを証明して確立されます。 **実行時間**： アルゴリズムの実行時間は中心経路法を使用して分析され、入力のサイズと入力空間の次元数に対してポリノミアル時間であることが示されます。 **実験結果**： アルゴリズムは現実世界のデータセットで既存の方法と比較され、精度と計算効率の両面で優れた性能を示しました。 **新奇性**： 提案されたアルゴリズムは以下の点で新奇です： * **確率的なもの**：確率的な方法とは異なり、保証された近似因子を持つ確率的な解決を提供します。 * **ポリノミアル時間**：大規模なデータセットに適用可能なポリノミアル時間の実行時間を持っています。 * **凸弛緩**：kSM問題の非凸性を扱うために凸弛緩技術を使用します。 **結論**： kSM-Approxアルゴリズムは、k次元中間値を計算するための既存の方法に対して顕著な改善を提供します。確率的な解決ではなく、確率的な解決を提供し、保証された近似因子を持つポリノミアル時間解決を提供することで、データ分析や機械学習におけるさまざまな応用において価値のあるツールとなります。


推奨論文

多目的ポートフォリオ最適化による勾配降下法

フォーミュラワン：競技プログラミングを超えたアルゴリズムの推理の深さを測定

知能型非晶質合金の設計のための材料ネットワーク表現の構築

フィードバックからチェックリストへの移行：AI生成の臨床記録の基盤評価

視覚と言語のトレーニングは分類学的知識の展開を助けますが、それを根本的に変えるものではありません

構造性能と製造性のバランスを取るための新しい多厚さトポロジー最適化法

非曲がり可能なガラス中間基板によって実現される高性能かつ熱的にも可能なマルチチップレットアーキテクチャの設計

連続変数間の一致を測定する新しい係数

物理学情報に基づくニューラルオペレータ（PINO）を使用して連結されたAllen-CahnとCahn-Hilliard相場方程式を学習する

証明書敏感な部分和問題：実例複雑度の達成