# The Optimization Landscape of Carath'eodory Decomposition of Toeplitz Covariances

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 39 references that are in the map.
- First posted on arXiv 3 Nov 2025.

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

- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [Loss landscapes and optimization in over-parameterized non-linear systems and neural networks](https://mlsanity.com/paper/2003.00307/) (2020)
- [Overparameterized Nonlinear Learning: Gradient Descent Takes the Shortest Path?](https://mlsanity.com/paper/1812.10004/) (2018)
- [Sample Efficient Toeplitz Covariance Estimation](https://mlsanity.com/paper/1905.05643/) (2019)
- [New Methods for MLE of Toeplitz Structured Covariance Matrices with Applications to RADAR Problems](https://mlsanity.com/paper/2307.03923/) (2023)
- [A Local Polyak-Lojasiewicz and Descent Lemma of Gradient Descent For Overparametrized Linear Models](https://mlsanity.com/paper/2505.11664/) (2025)
- [Block Acceleration Without Momentum: On Optimal Stepsizes of Block Gradient Descent for Least-Squares](https://mlsanity.com/paper/2405.16020/) (2024)
- [On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data](https://mlsanity.com/paper/1407.2490/) (2014)

## Abstract (arXiv)

Toeplitz covariance estimation is a classical signal processing problem, yet the geometry of the Gaussian maximum-likelihood objective remains only partially understood. Recent Newton-type, majorization-minimization, and gradient-based methods often solve the nonconvex problem globally with enough samples, but also reveal a difficult computational landscape. We study this phenomenon through an overparameterized Carath'eodory representation, which parameterizes the covariance by the frequencies and amplitudes of steering vectors. A simple example shows that, for any uniform frequency grid, optimizing only the amplitudes can leave a positive error even in the population setting, which motivates optimizing the frequencies as well. Our main result proves that this nonlinear parameterization adds no stationary points: for any sample covariance, every stationary point with a positive definite covariance gives a stationary point of the Toeplitz maximum-likelihood problem. In the population setting, every such point therefore recovers the true covariance. We also prove that gradient descent converges to the true covariance in the population setting, and to the unique maximum likelihood estimate when the sample covariance is close enough to the true covariance. These results do not require overparameterization. Numerically, overparameterization speeds up gradient descent and gives a more accurate estimate for a fixed number of iterations.