State space partitioning based on constrained spectral clustering for block particle filtering

• URL: http://arxiv.org/abs/2203.03475v1
• Date: Mon, 7 Mar 2022 15:45:47 GMT
• Title: State space partitioning based on constrained spectral clustering for block particle filtering
• Authors: Rui Min, Christelle Garnier, Fran\c{c}ois Septier, John Klein
• Abstract summary: The particle filter (PF) is a powerful inference tool widely used to estimate the filtering distribution in non-linear and/or non-Gaussian problems. To overcome the curse of dimensionality of PF, the block PF (BPF) inserts a blocking step to partition the state space into several subspaces or blocks of smaller dimension. Using blocks of small size reduces the variance of the filtering distribution estimate, but in turn the correlation between blocks is broken and a bias is introduced.
• Score: 7.32172860877574
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The particle filter (PF) is a powerful inference tool widely used to estimate the filtering distribution in non-linear and/or non-Gaussian problems. To overcome the curse of dimensionality of PF, the block PF (BPF) inserts a blocking step to partition the state space into several subspaces or blocks of smaller dimension so that the correction and resampling steps can be performed independently on each subspace. Using blocks of small size reduces the variance of the filtering distribution estimate, but in turn the correlation between blocks is broken and a bias is introduced. When the dependence relationships between state variables are unknown, it is not obvious to decide how to split the state space into blocks and a significant error overhead may arise from a poor choice of partitioning. In this paper, we formulate the partitioning problem in the BPF as a clustering problem and we propose a state space partitioning method based on spectral clustering (SC). We design a generalized BPF algorithm that contains two new steps: (i) estimation of the state vector correlation matrix from predicted particles, (ii) SC using this estimate as the similarity matrix to determine an appropriate partition. In addition, a constraint is imposed on the maximal cluster size to prevent SC from providing too large blocks. We show that the proposed method can bring together in the same blocks the most correlated state variables while successfully escaping the curse of dimensionality.

Related papers

• Scalable Context-Preserving Model-Aware Deep Clustering for Hyperspectral Images [51.95768218975529]
  Subspace clustering has become widely adopted for the unsupervised analysis of hyperspectral images (HSIs)<n>Recent model-aware deep subspace clustering methods often use a two-stage framework, involving the calculation of a self-representation matrix with complexity of O(n2), followed by spectral clustering.<n>We propose a scalable, context-preserving deep clustering method based on basis representation, which jointly captures local and non-local structures for efficient HSI clustering.
  arXiv  Detail & Related papers  (2025-06-12T16:43:09Z)
• PREAMBLE: Private and Efficient Aggregation of Block Sparse Vectors and Applications [42.968231105076335]
  We revisit the problem of secure aggregation of high-dimensional vectors in a two-server system such as Prio. PREAMBLE is a novel extension of distributed point functions that enables communication- and computation-efficient aggregation.
  arXiv  Detail & Related papers  (2025-03-14T21:58:15Z)
• Vector Copula Variational Inference and Dependent Block Posterior Approximations [3.4402084898030454]
  This paper proposes using vector copulas to capture dependence between the blocks parsimoniously. We call the resulting joint distribution a dependent block posterior'' approximation. The efficacy and versatility of the approach is demonstrated using four different statistical models and 16 datasets.
  arXiv  Detail & Related papers  (2025-03-03T00:24:54Z)
• Breaking the Memory Barrier: Near Infinite Batch Size Scaling for Contrastive Loss [59.835032408496545]
  We propose a tile-based strategy that partitions the contrastive loss calculation into arbitrary small blocks. We also introduce a multi-level tiling strategy to leverage the hierarchical structure of distributed systems. Compared to SOTA memory-efficient solutions, it achieves a two-order-of-magnitude reduction in memory while maintaining comparable speed.
  arXiv  Detail & Related papers  (2024-10-22T17:59:30Z)
• Weighted mesh algorithms for general Markov decision processes: Convergence and tractability [0.9940462449990576]
  We introduce a mesh-type approach for tackling discrete-time, finite-horizon Markov Decision Processes (MDPs) For unbounded state space the algorithm is "semi-tractable" in the sense that the complexity is $epsilonc$ with some dimension independent $cgeq2$.
  arXiv  Detail & Related papers  (2024-06-29T10:08:23Z)
• Faithful Density-Peaks Clustering via Matrix Computations on MPI Parallelization System [7.594123537718585]
  Density peaks clustering (DP) has the ability of detecting clusters of arbitrary shape and clustering non-Euclidean space data. We present a faithful and parallel DP method that makes use of two types of vector-like distance matrices and an inverse leading-node-finding policy. Our method is capable of clustering non-Euclidean data such as in community detection, while outperforming the state-of-the-art counterpart methods in accuracy when clustering large Euclidean data.
  arXiv  Detail & Related papers  (2024-06-18T06:05:45Z)
• Probing Hilbert space fragmentation and the block inverse participation ratio [0.0]
  We consider a family of quantum many-body Hamiltonians that show exact Hilbert space fragmentation in certain limits. The question arises whether fragmentation has implications for Hamiltonians in the vicinity of the subset defined by these exactly fragmented models. We present a modified inverse participation ratio (IPR) that is designed to capture the emergence of fragmented block structures.
  arXiv  Detail & Related papers  (2023-09-07T10:54:39Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  We introduce a new SBL inference algorithm that avoids explicit inversions of the covariance matrix. Our method can be up to thousands of times faster than existing baselines. We showcase how our new algorithm enables SBL to tractably tackle high-dimensional signal recovery problems.
  arXiv  Detail & Related papers  (2021-05-21T16:20:07Z)
• A Two Stage Generalized Block Orthogonal Matching Pursuit (TSGBOMP) Algorithm [0.3867363075280543]
  Recovery of an unknown sparse signal from a few of its projections is the key objective of compressed sensing. Existing block sparse recovery algorithms like BOMP make the assumption of uniform block size and known block boundaries. This paper proposes a two step procedure, where the first stage is a coarse block location identification stage. The second stage carries out finer localization of a non-zero cluster within the window selected in the first stage.
  arXiv  Detail & Related papers  (2020-08-18T17:00:55Z)
• Stochastic Bundle Adjustment for Efficient and Scalable 3D Reconstruction [43.736296034673124]
  Current bundle adjustment solvers such as the Levenberg-Marquardt (LM) algorithm are limited by the bottleneck in solving the Reduced Camera System (RCS) whose dimension is proportional to the camera number. We propose a bundle adjustment algorithm which seeks to decompose the RCS approximately inside the LM to improve the efficiency and scalability.
  arXiv  Detail & Related papers  (2020-08-02T10:26:09Z)
• Selective Inference for Latent Block Models [50.83356836818667]
  This study provides a selective inference method for latent block models. We construct a statistical test on a set of row and column cluster memberships of a latent block model. The proposed exact and approximated tests work effectively, compared to the naive test that did not take the selective bias into account.
  arXiv  Detail & Related papers  (2020-05-27T10:44:19Z)
• Computationally efficient sparse clustering [67.95910835079825]
  We provide a finite sample analysis of a new clustering algorithm based on PCA. We show that it achieves the minimax optimal misclustering rate in the regime $|theta infty$.
  arXiv  Detail & Related papers  (2020-05-21T17:51:30Z)

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.