Low-Rank Tensors for Multi-Dimensional Markov Models

• URL: http://arxiv.org/abs/2411.02098v1
• Date: Mon, 04 Nov 2024 14:06:49 GMT
• Title: Low-Rank Tensors for Multi-Dimensional Markov Models
• Authors: Madeline Navarro, Sergio Rozada, Antonio G. Marques, Santiago Segarra,
• Abstract summary: We present low-rank tensors for representing transition probabilities on multi-dimensional state spaces. Our proposed model yields a parsimonious representation with fewer parameters than matrix-based approaches.
• Score: 33.35376484951434
• License:
• Abstract: This work presents a low-rank tensor model for multi-dimensional Markov chains. A common approach to simplify the dynamical behavior of a Markov chain is to impose low-rankness on the transition probability matrix. Inspired by the success of these matrix techniques, we present low-rank tensors for representing transition probabilities on multi-dimensional state spaces. Through tensor decomposition, we provide a connection between our method and classical probabilistic models. Moreover, our proposed model yields a parsimonious representation with fewer parameters than matrix-based approaches. Unlike these methods, which impose low-rankness uniformly across all states, our tensor method accounts for the multi-dimensionality of the state space. We also propose an optimization-based approach to estimate a Markov model as a low-rank tensor. Our optimization problem can be solved by the alternating direction method of multipliers (ADMM), which enjoys convergence to a stationary solution. We empirically demonstrate that our tensor model estimates Markov chains more efficiently than conventional techniques, requiring both fewer samples and parameters. We perform numerical simulations for both a synthetic low-rank Markov chain and a real-world example with New York City taxi data, showcasing the advantages of multi-dimensionality for modeling state spaces.

Related papers

• NeurAM: nonlinear dimensionality reduction for uncertainty quantification through neural active manifolds [0.6990493129893112]
  We leverage autoencoders to discover a one-dimensional neural active manifold (NeurAM) capturing the model output variability. We show how NeurAM can be used to obtain multifidelity sampling estimators with reduced variance.
  arXiv  Detail & Related papers  (2024-08-07T04:27:58Z)
• Chebyshev Particles [0.0]
  We are first to consider the posterior distribution of the objective as a mapping of samples in an infinite-dimensional Euclidean space. We propose a new criterion by maximizing the weighted Riesz polarization quantity, to discretize rectifiable submanifolds via pairwise interaction. We have achieved high performance from the experiments for parameter inference in a linear state-space model with synthetic data and a non-linear volatility model with real-world data.
  arXiv  Detail & Related papers  (2023-09-10T16:40:30Z)
• Differentiating Metropolis-Hastings to Optimize Intractable Densities [51.16801956665228]
  We develop an algorithm for automatic differentiation of Metropolis-Hastings samplers. We apply gradient-based optimization to objectives expressed as expectations over intractable target densities.
  arXiv  Detail & Related papers  (2023-06-13T17:56:02Z)
• A Stochastic Newton Algorithm for Distributed Convex Optimization [62.20732134991661]
  We analyze a Newton algorithm for homogeneous distributed convex optimization, where each machine can calculate gradients of the same population objective. We show that our method can reduce the number, and frequency, of required communication rounds compared to existing methods without hurting performance.
  arXiv  Detail & Related papers  (2021-10-07T17:51:10Z)
• Jointly Modeling and Clustering Tensors in High Dimensions [6.072664839782975]
  We consider the problem of jointly benchmarking and clustering of tensors. We propose an efficient high-maximization algorithm that converges geometrically to a neighborhood that is within statistical precision.
  arXiv  Detail & Related papers  (2021-04-15T21:06:16Z)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Estimation of Switched Markov Polynomial NARX models [75.91002178647165]
  We identify a class of models for hybrid dynamical systems characterized by nonlinear autoregressive (NARX) components. The proposed approach is demonstrated on a SMNARX problem composed by three nonlinear sub-models with specific regressors.
  arXiv  Detail & Related papers  (2020-09-29T15:00:47Z)
• A Dynamical Mean-Field Theory for Learning in Restricted Boltzmann Machines [2.8021833233819486]
  We define a message-passing algorithm for computing magnetizations in Boltzmann machines. We prove the global convergence of the algorithm under a stability criterion and compute convergence rates showing excellent agreement with numerical simulations.
  arXiv  Detail & Related papers  (2020-05-04T15:19:31Z)
• Multi-View Spectral Clustering Tailored Tensor Low-Rank Representation [105.33409035876691]
  This paper explores the problem of multi-view spectral clustering (MVSC) based on tensor low-rank modeling. We design a novel structured tensor low-rank norm tailored to MVSC. We show that the proposed method outperforms state-of-the-art methods to a significant extent.
  arXiv  Detail & Related papers  (2020-04-30T11:52:12Z)

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.