# Low-Rank Tensors for Multi-Dimensional Markov Models

arXiv: https://arxiv.org/abs/2411.02098 · HTML: https://mlsanity.com/paper/2411.02098/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 48 references that are in the map.
- First posted on arXiv 4 Nov 2024.

## Builds on (most cited first, 15 of 15)

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview](https://mlsanity.com/paper/1809.09573/) (2018)
- [Global Convergence of ADMM in Nonconvex Nonsmooth Optimization](https://mlsanity.com/paper/1511.06324/) (2015)
- [A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization](https://mlsanity.com/paper/1506.04209/) (2015)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Tensors, Learning, and 'Kolmogorov Extension' for Finite-alphabet Random Vectors](https://mlsanity.com/paper/1712.00205/) (2017)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective](https://mlsanity.com/paper/2006.08183/) (2020)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions](https://mlsanity.com/paper/1611.04706/) (2016)
- [On Learning Markov Chains](https://mlsanity.com/paper/1810.11754/) (2018)
- [Learning Markov models via low-rank optimization](https://mlsanity.com/paper/1907.00113/) (2019)
- [Estimation of Markov Chain via Rank-Constrained Likelihood](https://mlsanity.com/paper/1804.00795/) (2018)
- [Recovering Structured Probability Matrices](https://mlsanity.com/paper/1602.06586/) (2016)
- [CP-MDP: A CANDECOMP-PARAFAC Decomposition Approach to Solve a Markov Decision Process Multidimensional Problem](https://mlsanity.com/paper/2103.00331/) (2021)

## Built on by (most cited first, 2 of 2)

- [Modes of Sequence Models and Learning Coefficients](https://mlsanity.com/paper/2504.18048/) (2025)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)

## Abstract (arXiv)

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.