Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis
Abstract
We study the estimation of a K-dimensional simplex from N i.i.d.\ points sampled uniformly from its interior; the observations are convex combinations of K+1 unknown prototypes. Existing polynomial-time estimators need cubic per-sample work or O(NK) storage and are impractical at N∼ 106--108. We propose DeepMVSA, which re-expresses the minimum-volume principle in neural implicit form: a lightweight coordinate network generates the mixing weights and a triangular LU-type parameterization the dual simplex matrix, reducing the trainable-state memory to O(K2), independent of N, and the cost per data pass to O(NK2). We prove a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator; an oracle inequality for every global minimizer of the neural objective, with volume-inflation control and an explicit shrinkage bias; a conditional end-to-end error budget separating statistical, approximation, optimization, and enclosure-residual terms on an explicit envelope event; and two-point lower bounds: at any noise level σ>0 fixed independently of N, the N−1/2 scaling is unimprovable in its N-exponent. Experiments with up to N=108 synthetic observations are consistent with the predicted accuracy and scaling, and feasibility on real scenes of ∼ 107 pixels is demonstrated.
Related
- Minimum-coordinate elimination on a simplex: polynomial first-step safety and coNP-complete correctness
- From the Steiner Inellipse to the John Ellipsoid of a Simplex: A Corner-Volume Characterization
- Minimum central circles: an effective characterization of the global asymptotic constant
- Bandwidth rules for Dirichlet kernel density estimation on the simplex
- Minimum Volume Optimal Transport for Multivariate Conformal Prediction
BibTeX
@misc{li2026scalable,
title = {{Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis}},
author = {Jun Li and Yanlong Guo and Zhaozhao Zeng},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25576},
eprint = {2609.25576},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25576},
}
RIS
TY - UNPB
TI - Scalable Minimum-Volume Simplex Estimation with Non-asymptotic Analysis
AU - Jun Li
AU - Yanlong Guo
AU - Zhaozhao Zeng
PY - 2026
DA - 2026/09/25
PB - arXiv
DO - 10.48550/arxiv.2609.25576
UR - https://arxiv.org/abs/2609.25576
AB - We study the estimation of a K-dimensional simplex from N i.i.d.\ points sampled uniformly from its interior; the observations are convex combinations of K+1 unknown prototypes. Existing polynomial-time estimators need cubic per-sample work or O(NK) storage and are impractical at N∼ 10^6--10^8. We propose DeepMVSA, which re-expresses the minimum-volume principle in neural implicit form: a lightweight coordinate network generates the mixing weights and a triangular LU-type parameterization the dual simplex matrix, reducing the trainable-state memory to O(K^2), independent of N, and the cost per data pass to O(NK^2). We prove a non-asymptotic sample-complexity bound of the polynomial-time benchmark order for a localized surrogate estimator; an oracle inequality for every global minimizer of the neural objective, with volume-inflation control and an explicit shrinkage bias; a conditional end-to-end error budget separating statistical, approximation, optimization, and enclosure-residual terms on an explicit envelope event; and two-point lower bounds: at any noise level σ>0 fixed independently of N, the N^−1/2 scaling is unimprovable in its N-exponent. Experiments with up to N=10^8 synthetic observations are consistent with the predicted accuracy and scaling, and feasibility on real scenes of ∼ 10^7 pixels is demonstrated.
ER -