Optimal estimation and completion of matrices with biclustering structures

MaRDI QIDQ2834492zbMATH OpenFDO

Authors Chao Gao, Yu Lu, Zongming Ma, Harrison H. Zhou

Publication date 22 November 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1512.00150, http://jmlr.csail.mit.edu/papers/v17/15-617.html

zbMATH Keywords

biclusteringgraphonmatrix completionmissing datasparse networkstochastic block models

Mathematics Subject Classification ID

Nonparametric estimation (62G05) Estimation in multivariate analysis (62H12) Classification and discrimination; cluster analysis (statistical aspects) (62H30)

Abstract: Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a unified theory for the estimation and completion of matrices with biclustering structures, where the data is a partially observed and noise contaminated data matrix with a certain biclustering structure. In particular, we show that a constrained least squares estimator achieves minimax rate-optimal performance in several of the most important scenarios. To this end, we derive unified high probability upper bounds for all sub-Gaussian data and also provide matching minimax lower bounds in both Gaussian and binary cases. Due to the close connection of graphon to stochastic block models, an immediate consequence of our general results is a minimax rate-optimal estimator for sparse graphons.

Recommendations

• Structured matrix estimation and completion
• Robust matrix completion
• A Bayesian approach for noisy matrix completion: optimal rate under general sampling distribution
• Matrix estimation by universal singular value thresholding
• Local inference by penalization method for biclustering model

Cited in

(26)

• Local inference by penalization method for biclustering model
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Subspace estimation from unbalanced and incomplete data matrices: \({\ell_{2,\infty}}\) statistical guarantees
• Edgeworth expansions for network moments
• Local-density dependent Markov processes on graphons with epidemiological applications
• Bootstrapping exchangeable random graphs
• Biclustering via structured regularized matrix decomposition
• Generalized co-clustering analysis via regularized alternating least squares
• Outlier detection in networks with missing links
• Maximum likelihood estimation of sparse networks with missing observations
• Profile likelihood biclustering
• Dynamic network models and graphon estimation
• Structured matrix estimation and completion
• Universal latent space model fitting for large networks with edge covariates
• Optimal bipartite network clustering
• Bayesian model selection with graph structured sparsity
• Hierarchical Community Detection by Recursive Partitioning
• Graphon estimation via nearest‐neighbour algorithm and two‐dimensional fused‐lasso denoising
• Network online change point localization
• Asymptotic analysis of statistical estimators related to multigraphex processes under misspecification
• Network Estimation by Mixing: Adaptivity and More
• Tractably modelling dependence in networks beyond exchangeability
• Beyond symmetry: best submatrix selection for the sparse truncated SVD
• Computational lower bounds for graphon estimation via low-degree polynomials
• Statistical and Computational Efficiency for Smooth Tensor Estimation with Unknown Permutations
• Conformal link prediction for false discovery rate control

This page was built for publication: Optimal estimation and completion of matrices with biclustering structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2834492)