論文の概要: Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS
- arxiv url: http://arxiv.org/abs/2611.15810v1
- Date: Wed, 11 Nov 2026 18:26:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:33.249728
- Title: Sparse PCA with Overlapping Supports: NP-Hardness and an FPTAS
- Title(参考訳): 重なり合うサポートを持つスパースPCA:NP-HardnessとFPTAS
- Abstract要約: 個別の空間定数と任意の支持重なりを持つ一般モデルについて検討する。
SPCA は $r = d = 2$ であっても NP-hard であるが、$r$ と $d$ が固定されたとき、フルタイム近似スキーム (FPTAS) を認める。
- 参考スコア(独自算出の注目度): 4.239775815863115
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In sparse principal component analysis (SPCA) with several components, each must be sparse and all must be pairwise orthogonal. When the supports of the components overlap, these two requirements interact. For a covariance matrix of fixed rank, polynomial-time algorithms with optimality or approximation guarantees are known for one component, and for several components with disjoint supports or with a common support. We study the general model, with individual sparsity constants and arbitrary support overlaps. We are given a rational $n\times r$ matrix $R$ and $d$ sparsity constants $s_i \le n$, and the goal is to find an $n\times d$ matrix $X$ with orthonormal columns that maximizes $\|R^\top X\|_F^2$, such that column $i$ has at most $s_i$ non-zero entries. Here $RR^\top$ plays the role of the covariance matrix and has rank at most $r$. We show that SPCA is NP-hard even when $r = d = 2$, but admits a fully polynomial-time approximation scheme (FPTAS) when $r$ and $d$ are fixed. The returned solution has exactly orthonormal columns, and its entries are real algebraic numbers in an exact representation. For fixed $ε$, the number of steps of the algorithm is linear in $n$ up to a polylogarithmic factor. Our approach reduces SPCA to a sparse version of the orthogonal Procrustes problem, that is, to maximizing a linear function over the feasible region of SPCA. We show that this problem is NP-hard even for $d = 2$, and we give an FPTAS for it when $d$ is fixed. This FPTAS combines approximate dynamic programming over the rows, two-column updates that restore exact orthogonality, and an exact computation of the few variables for which these updates are not available.
- Abstract(参考訳): 複数の成分を持つスパース主成分分析(SPCA)では、それぞれがスパースでなければならない。
コンポーネントのサポートが重複すると、これらの2つの要件が相互作用します。
固定階数の共分散行列では、最適性あるいは近似保証を持つ多項式時間アルゴリズムが1つの成分に対して知られ、不連結な支持を持ついくつかの成分や共通の支持を持つ。
個別の空間定数と任意の支持重なりを持つ一般モデルについて検討する。
有理な$n\times r$ matrix $R$ と $d$スペーサリティ定数 $s_i \le n$ が与えられ、目的は、$n\times d$ matrix $X$ と、$\|R^\top X\|_F^2$ を最大とする正規直交列を見つけることである。
ここで$RR^\top$は共分散行列の役割を担い、最大$r$のランクを持つ。
SPCA は $r = d = 2$ であっても NP-hard であるが、$r$ と $d$ が固定されたとき、完全多項式時間近似スキーム (FPTAS) を認める。
返却された解は、正確に正則な列を持ち、そのエントリは、正確な表現における実代数的数である。
固定$ε$の場合、アルゴリズムのステップの数はポリ対数係数まで$n$で線型である。
提案手法では,SPCA を直交する Procrustes 問題,すなわち SPCA の可能な領域上の線形関数を最大化するために,スパース版に還元する。
この問題は$d = 2$であってもNPハードであることを示し、$d$が固定されたときにFPTASを与える。
このFPTASは行上の近似動的プログラミングと、正確な直交性を復元する2列更新と、これらの更新が利用できない少数の変数の正確な計算を組み合わせる。
関連論文リスト
- Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma [70.99943094379263]
有界ラディウス系におけるスパース半定値プログラムに対する最初の準時間古典的解法を与える。
我々の主な技術的貢献は、ハミルトンのギブス状態を同時に表す古典的な手続きである。
論文 参考訳(メタデータ) (2026-09-30T17:51:21Z) - A Sharp Barrier for Consistent Submodular Maximization: Any Improvement over $2-\sqrt{2}$ Entails Exponential Queries or Linear Recourse [50.69285844345291]
我々は、要素が時間とともに到着する際のソリューションの品質と安定性のトレードオフについて研究する。
我々のアルゴリズムは,有理オラクル$を$O(varepsilon-1)$recourseで実装し,そのアルゴリズムから普遍価格証明書の存在を分離する。
論文 参考訳(メタデータ) (2026-09-09T10:13:43Z) - On the Complexity of Low-Rank Matrix Signing and Entrywise Power Matrix Factorization [9.842769671181276]
我々は、入出力行列分解(EPMF)がNPハードであることを示し、$r=2$は最小の非自明ケースである。
EPMF は与えられた行列の成分の符号を$X$で反転させ、ランク-$r$行列を得る問題と同値である。
論文 参考訳(メタデータ) (2026-07-06T09:50:20Z) - A Fast and Accurate Approach for Covariance Matrix Construction [0.0]
Reichel (2025) は、バリアンスを $mathrmBariance(x)=frac1n(n-1)sum_ij(x_i-x_j)2$ と定義した。
これを共分散行列に拡張するには、$mathrmCov(X)=frac1n-1!left(Xtop X-frac1n,s,stopright)$ with $s=Xtop mathbf1
論文 参考訳(メタデータ) (2025-11-11T13:27:05Z) - 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) - Solving Dense Linear Systems Faster Than via Preconditioning [1.8854491183340518]
我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$であることを示す。
特に、我々のアルゴリズムは$tilde O(n2)$ if $k=O(n0.729)$である。
主アルゴリズムはランダム化ブロック座標降下法とみなすことができる。
論文 参考訳(メタデータ) (2023-12-14T12:53:34Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳(メタデータ) (2022-09-30T04:15:44Z) - 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) - Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean
Estimation [58.24280149662003]
本稿では,データセットの大部分を敵が破壊できるリストデコタブル平均推定の問題について検討する。
我々は、ほぼ最適な統計的保証を達成するために、リストデコダブル平均推定のための新しいアルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-06-16T03:34:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。