High-dimensional Clustering and Signal Recovery under Block Signals

• URL: http://arxiv.org/abs/2504.08332v1
• Date: Fri, 11 Apr 2025 07:54:55 GMT
• Title: High-dimensional Clustering and Signal Recovery under Block Signals
• Authors: Wu Su, Yumou Qiu,
• Abstract summary: We propose two sets of methods, cross-block feature aggregation PCA (CFA-PCA) and moving average PCA (MA-PCA)<n>Both methods adaptively utilize block signal structures, applicable to non-Gaussian data with heterogeneous covariance matrices.<n>We show that the proposed methods can achieve the minimax lower bounds (CMLB) for the sparse and dense block signal regimes.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper studies computationally efficient methods and their minimax optimality for high-dimensional clustering and signal recovery under block signal structures. We propose two sets of methods, cross-block feature aggregation PCA (CFA-PCA) and moving average PCA (MA-PCA), designed for sparse and dense block signals, respectively. Both methods adaptively utilize block signal structures, applicable to non-Gaussian data with heterogeneous variances and non-diagonal covariance matrices. Specifically, the CFA method utilizes a block-wise U-statistic to aggregate and select block signals non-parametrically from data with unknown cluster labels. We show that the proposed methods are consistent for both clustering and signal recovery under mild conditions and weaker signal strengths than the existing methods without considering block structures of signals. Furthermore, we derive both statistical and computational minimax lower bounds (SMLB and CMLB) for high-dimensional clustering and signal recovery under block signals, where the CMLBs are restricted to algorithms with polynomial computation complexity. The minimax boundaries partition signals into regions of impossibility and possibility. No algorithm (or no polynomial time algorithm) can achieve consistent clustering or signal recovery if the signals fall into the statistical (or computational) region of impossibility. We show that the proposed CFA-PCA and MA-PCA methods can achieve the CMLBs for the sparse and dense block signal regimes, respectively, indicating the proposed methods are computationally minimax optimal. A tuning parameter selection method is proposed based on post-clustering signal recovery results. Simulation studies are conducted to evaluate the proposed methods. A case study on global temperature change demonstrates their utility in practice.

Related papers

• Group Projected Subspace Pursuit for Block Sparse Signal Reconstruction: Convergence Analysis and Applications [4.297249011611168]
  We present a convergence analysis of the Group Projected Subspace Pursuit (GPSP) algorithm. GPSP recovers the true block sparse signals when the observations are noisy. We find that GPSP outperforms other algorithms in most cases for various levels of block sparsity and block sizes.
  arXiv  Detail & Related papers  (2024-06-01T08:48:06Z)
• Adaptive Block Sparse Regularization under Arbitrary Linear Transform [7.0326155922512275]
  We propose a convex and fast signal reconstruction method for block sparsity under arbitrary linear transform with unknown block structure. Our work broadens the scope of block sparse regularization, enabling more versatile and powerful applications across various signal processing domains.
  arXiv  Detail & Related papers  (2024-01-27T04:24:19Z)
• Linearized Wasserstein dimensionality reduction with approximation guarantees [65.16758672591365]
  LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space. We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size. We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
  arXiv  Detail & Related papers  (2023-02-14T22:12:16Z)
• Fast conformational clustering of extensive molecular dynamics simulation data [19.444636864515726]
  We present an unsupervised data processing workflow that is specifically designed to obtain a fast conformational clustering of long trajectories. We combine two dimensionality reduction algorithms (cc_analysis and encodermap) with a density-based spatial clustering algorithm (HDBSCAN) With the help of four test systems we illustrate the capability and performance of this clustering workflow.
  arXiv  Detail & Related papers  (2023-01-11T14:36:43Z)
• Exploiting Temporal Structures of Cyclostationary Signals for Data-Driven Single-Channel Source Separation [98.95383921866096]
  We study the problem of single-channel source separation (SCSS) We focus on cyclostationary signals, which are particularly suitable in a variety of application domains. We propose a deep learning approach using a U-Net architecture, which is competitive with the minimum MSE estimator.
  arXiv  Detail & Related papers  (2022-08-22T14:04:56Z)
• An Accelerated Doubly Stochastic Gradient Method with Faster Explicit Model Identification [97.28167655721766]
  We propose a novel doubly accelerated gradient descent (ADSGD) method for sparsity regularized loss minimization problems. We first prove that ADSGD can achieve a linear convergence rate and lower overall computational complexity.
  arXiv  Detail & Related papers  (2022-08-11T22:27:22Z)
• Signed Cumulative Distribution Transform for Parameter Estimation of 1-D Signals [0.0]
  The method builds upon signal estimation using the cumulative distribution transform (CDT) originally introduced for positive distributions. We show that Wasserstein-type distance minimization can be performed simply using linear least squares techniques in SCDT space for arbitrary signal classes.
  arXiv  Detail & Related papers  (2022-07-16T17:44:29Z)
• Deep Equilibrium Assisted Block Sparse Coding of Inter-dependent Signals: Application to Hyperspectral Imaging [71.57324258813675]
  A dataset of inter-dependent signals is defined as a matrix whose columns demonstrate strong dependencies. A neural network is employed to act as structure prior and reveal the underlying signal interdependencies. Deep unrolling and Deep equilibrium based algorithms are developed, forming highly interpretable and concise deep-learning-based architectures.
  arXiv  Detail & Related papers  (2022-03-29T21:00:39Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLE is a dimensionality-reduction post-processing step that corrects an initial embedding by minimizing a loss functional with both a local, metric term and a global, topological term. We observe that DIPOLE outperforms popular methods like UMAP, t-SNE, and Isomap on a number of popular datasets.
  arXiv  Detail & Related papers  (2021-06-14T17:19:44Z)
• Lattice partition recovery with dyadic CART [79.96359947166592]
  We study piece-wise constant signals corrupted by additive Gaussian noise over a $d$-dimensional lattice. Data of this form naturally arise in a host of applications, and the tasks of signal detection or testing, de-noising and estimation have been studied extensively in the statistical and signal processing literature. In this paper we consider instead the problem of partition recovery, i.e.of estimating the partition of the lattice induced by the constancy regions of the unknown signal. We prove that a DCART-based procedure consistently estimates the underlying partition at a rate of order $sigma2 k*
  arXiv  Detail & Related papers  (2021-05-27T23:41:01Z)
• Hierarchical compressed sensing [5.39680014668952]
  Compressed sensing is a paradigm within signal processing that provides the means for recovering structured signals from linear measurements. We present recovery algorithms based on efficient hierarchical hard-thresholding. Building upon this machinery, we sketch practical applications of this framework in machine-type communications and quantum tomography.
  arXiv  Detail & Related papers  (2021-04-06T18:00:01Z)

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.