Optimal rates of statistical seriation
From MaRDI portal
Publication:1715546
Abstract: Given a matrix the seriation problem consists in permuting its rows in such way that all its columns have the same shape, for example, they are monotone increasing. We propose a statistical approach to this problem where the matrix of interest is observed with noise and study the corresponding minimax rate of estimation of the matrices. Specifically, when the columns are either unimodal or monotone, we show that the least squares estimator is optimal up to logarithmic factors and adapts to matrices with a certain natural structure. Finally, we propose a computationally efficient estimator in the monotonic case and study its performance both theoretically and experimentally. Our work is at the intersection of shape constrained estimation and recent work that involves permutation learning, such as graph denoising and ranking.
Recommendations
Cites work
- A new perspective on least squares under convex constraint
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- A survey for the quadratic assignment problem
- Abundance matrices and seriation in archaeology
- Adaptive risk bounds in unimodal regression
- Algorithm AS 257: Isotonic Regression for Umbrella Orderings
- An Empirical Distribution Function for Sampling with Incomplete Information
- Binary choice probabilities: on the varieties of stochastic transitivity
- Computational barriers in minimax submatrix detection
- Estimating a regression function
- Estimating a smooth monotone regression function
- Estimation in Tournaments and Graphs Under Monotonicity Constraints
- Estimation of unimodal densities without smoothness assumptions
- Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons
- Flinders Petrie, the travelling salesman problem, and the beginning of mathematical modeling in archaeology
- Hellinger-consistency of certain nonparametric maximum likelihood estimators
- scientific article; zbMATH DE number 3727563 (Why is no real title available?)
- scientific article; zbMATH DE number 49190 (Why is no real title available?)
- scientific article; zbMATH DE number 193111 (Why is no real title available?)
- scientific article; zbMATH DE number 854949 (Why is no real title available?)
- scientific article; zbMATH DE number 3390139 (Why is no real title available?)
- Incidence matrices with the consecutive 1’s property
- Incidence matrices, interval graphs and seriation in archeology
- Introduction to nonparametric estimation
- Learning \(k\)-modal distributions via testing
- Learning without concentration
- Least squares estimators of the mode of a unimodal regression function
- Linear time isotonic and unimodal regression in the \(L_{1}\) and \(L_{\infty }\) norms
- Living on the edge: phase transitions in convex programs with random data
- Locally adaptive regression splines
- Matrix estimation by universal singular value thresholding
- Maximum likelihood estimation of smooth monotone and unimodal densities.
- Minimax rates in permutation estimation for feature matching
- On matrix estimation under monotonicity constraints
- On risk bounds in isotonic and other shape restricted regression problems
- On testing consecutive-ones property in parallel
- Optimal detection of sparse principal components in high dimension
- Optimal rates of statistical seriation
- PIECEWISE-POLYNOMIAL APPROXIMATIONS OF FUNCTIONS OF THE CLASSES $ W_{p}^{\alpha}$
- Rate of convergence of nonparametric estimates of maximum-likelihood type
- Rate-optimal graphon estimation
- Risk bounds in isotonic regression
- Seriation and matrix reordering methods: An historical overview
- Sharp oracle bounds for monotone and convex regression through aggregation
- Sharp oracle inequalities for least squares estimators in shape restricted regression
- Stochastically Transitive Models for Pairwise Comparisons: Statistical and Computational Issues
- Testing k-modal distributions: optimal algorithms via reductions
- The convex geometry of linear inverse problems
- Unimodal density estimation using Bernstein polynomials
- Unimodal regression using Bernstein–Schoenberg splines and penalties
- Unimodal regression via prefix isotonic regression
Cited in
(32)- Linear regression with sparsely permuted data
- Adaptive risk bounds in unimodal regression
- Optimal rates of statistical seriation
- Nonparametric shape-restricted regression
- Sharp oracle inequalities for least squares estimators in shape restricted regression
- Towards optimal estimation of bivariate isotonic matrices with unknown permutations
- Optimal detection of the feature matching map in presence of noise and outliers
- Isotonic regression with unknown permutations: statistics, computation and adaptation
- Reconstruction of line-embeddings of graphons
- Cut norm discontinuity of triangular truncation of graphons
- Worst-case versus average-case design for estimation from partial pairwise comparisons
- Estimation of Monge matrices
- Adaptive confidence sets in shape restricted regression
- Minimax rates in permutation estimation for feature matching
- scientific article; zbMATH DE number 3868419 (Why is no real title available?)
- Convex relaxations for permutation problems
- An Optimal Algorithm for Strict Circular Seriation
- Two-stage approach to multivariate linear regression with sparsely mismatched data
- Low permutation-rank matrices: structural properties and noisy completion
- Learning Theory and Kernel Machines
- An optimization parameter for seriation of noisy data
- Optimal Permutation Recovery in Permuted Monotone Matrix Model
- Optimal permutation estimation in crowdsourcing problems
- Graph sequences sampled from Robinson graphons
- Robust recovery of Robinson property in L^p-graphons: a cut-norm approach
- Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
- Covariance alignment: from maximum likelihood estimation to Gromov-Wasserstein
- Minimax optimal rates of convergence in monotone shuffled and unlinked regression models under vanishing noise
- Optimal level set estimation for non-parametric tournament and crowdsourcing problems
- Should we augment large covariance matrix estimation with auxiliary network information?
- Minimax optimal seriation in polynomial time
- Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs
This page was built for publication: Optimal rates of statistical seriation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1715546)
