sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation

• URL: http://arxiv.org/abs/2506.08670v1
• Date: Tue, 10 Jun 2025 10:30:48 GMT
• Title: sparseGeoHOPCA: A Geometric Solution to Sparse Higher-Order PCA Without Covariance Estimation
• Authors: Renjie Xu, Chong Wu, Maolin Che, Zhuoheng Ran, Yimin Wei, Hong Yan,
• Abstract summary: We propose a novel framework for high-order principal component analysis (SHOPCA) that introduces a perspective to tensor-dependent decomposition.<n>We show that sparseGeoHOP supports in high-dimensional image settings and on ImageNet.
• Score: 8.802387139798808
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose sparseGeoHOPCA, a novel framework for sparse higher-order principal component analysis (SHOPCA) that introduces a geometric perspective to high-dimensional tensor decomposition. By unfolding the input tensor along each mode and reformulating the resulting subproblems as structured binary linear optimization problems, our method transforms the original nonconvex sparse objective into a tractable geometric form. This eliminates the need for explicit covariance estimation and iterative deflation, enabling significant gains in both computational efficiency and interpretability, particularly in high-dimensional and unbalanced data scenarios. We theoretically establish the equivalence between the geometric subproblems and the original SHOPCA formulation, and derive worst-case approximation error bounds based on classical PCA residuals, providing data-dependent performance guarantees. The proposed algorithm achieves a total computational complexity of $O\left(\sum_{n=1}^{N} (k_n^3 + J_n k_n^2)\right)$, which scales linearly with tensor size. Extensive experiments demonstrate that sparseGeoHOPCA accurately recovers sparse supports in synthetic settings, preserves classification performance under 10$\times$ compression, and achieves high-quality image reconstruction on ImageNet, highlighting its robustness and versatility.

Related papers

• Outlier-aware Tensor Robust Principal Component Analysis with Self-guided Data Augmentation [21.981038455329013]
  We propose a self-guided data augmentation approach that employs adaptive weighting to suppress outlier influence.<n>We show the improvements in both accuracy and computational efficiency compared to state-of-the-art methods.
  arXiv  Detail & Related papers  (2025-04-25T13:03:35Z)
• Solve sparse PCA problem by employing Hamiltonian system and leapfrog method [0.0]
  We propose a novel sparse PCA algorithm that imposes sparsity through a smooth L1 penalty.<n> Experimental evaluations on a face recognition dataset-using both k-nearest neighbor and kernel ridge regressions-demonstrate that the proposed sparse PCA methods consistently achieve higher classification accuracy than conventional PCA.
  arXiv  Detail & Related papers  (2025-03-30T06:39:11Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  This paper presents a theoretical analysis of linearahead as a principled method for stabilizing (large-scale) neural network training. We argue that instabilities in the optimization process are often caused by the nonmonotonicity of the loss landscape and show how linear can help by leveraging the theory of nonexpansive operators.
  arXiv  Detail & Related papers  (2023-10-20T12:45:12Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  This paper proposes a flexible algorithmic framework for graph learning under low-rank structural constraints. The problem is expressed as penalized maximum likelihood estimation of an elliptical distribution. We leverage geometries of positive definite matrices and positive semi-definite matrices of fixed rank that are well suited to elliptical models.
  arXiv  Detail & Related papers  (2022-10-21T13:19:45Z)
• Adaptive Zeroth-Order Optimisation of Nonconvex Composite Objectives [1.7640556247739623]
  We analyze algorithms for zeroth-order entropy composite objectives, focusing on dependence on dimensionality. This is achieved by exploiting low dimensional structure of the decision set using the mirror descent method with an estimation alike function. To improve the gradient, we replace the classic sampling method based on Rademacher and show that the mini-batch method copes with non-Eucli geometry.
  arXiv  Detail & Related papers  (2022-08-09T07:36:25Z)
• Hybrid Model-based / Data-driven Graph Transform for Image Coding [54.31406300524195]
  We present a hybrid model-based / data-driven approach to encode an intra-prediction residual block. The first $K$ eigenvectors of a transform matrix are derived from a statistical model, e.g., the asymmetric discrete sine transform (ADST) for stability. Using WebP as a baseline image, experimental results show that our hybrid graph transform achieved better energy compaction than default discrete cosine transform (DCT) and better stability than KLT.
  arXiv  Detail & Related papers  (2022-03-02T15:36:44Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Piecewise linear regression and classification [0.20305676256390928]
  This paper proposes a method for solving multivariate regression and classification problems using piecewise linear predictors. A Python implementation of the algorithm described in this paper is available at http://cse.lab.imtlucca.it/bemporad/parc.
  arXiv  Detail & Related papers  (2021-03-10T17:07:57Z)
• Last iterate convergence of SGD for Least-Squares in the Interpolation regime [19.05750582096579]
  We study the noiseless model in the fundamental least-squares setup. We assume that an optimum predictor fits perfectly inputs and outputs $langle theta_*, phi(X) rangle = Y$, where $phi(X)$ stands for a possibly infinite dimensional non-linear feature map.
  arXiv  Detail & Related papers  (2021-02-05T14:02:20Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Alternating minimization algorithms for graph regularized tensor completion [8.26185178671935]
  We consider a Canonical Polyadic (CP) decomposition approach to low-rank tensor completion (LRTC) The usage of graph regularization entails benefits in the learning accuracy of LRTC, but at the same time, induces coupling graph Laplacian terms. We propose efficient alternating minimization algorithms by leveraging the block structure of the underlying CP decomposition-based model.
  arXiv  Detail & Related papers  (2020-08-28T23:20:49Z)
• An Optimal Statistical and Computational Framework for Generalized Tensor Estimation [10.899518267165666]
  This paper describes a flexible framework for low-rank tensor estimation problems. It includes many important instances from applications in computational imaging, genomics, and network analysis.
  arXiv  Detail & Related papers  (2020-02-26T01:54:35Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.