Optimal Estimation and Completion of Matrices with Biclustering Structures

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.

References in corpus (1)

• Graph limits and exchangeable random graphs

Cited by in corpus (26)

• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices
• Estimating network edge probabilities by neighborhood smoothing
• Network cross-validation by edge sampling
• Consistency of Maximum Likelihood for Continuous-Space Network Models I
• Bootstrapping Exchangeable Random Graphs
• Statistical Inferences of Linear Forms for Noisy Matrix Completion
• Exploration of Large Networks with Covariates via Fast and Universal Latent Space Model Fitting
• Hierarchical community detection by recursive partitioning
• Exact Clustering in Tensor Block Model: Statistical Optimality and Computational Limit
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Optimal Bipartite Network Clustering
• Exact Minimax Estimation for Phase Synchronization
• General framework for projection structures
• 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
• Change-Point Detection in Dynamic Networks with Missing Links
• Lattice partition recovery with dyadic CART
• Maximum Likelihood Estimation of Sparse Networks with Missing Observations
• Euclidean Representation of Low-Rank Matrices and Its Statistical Applications
• Bayesian Model Selection with Graph Structured Sparsity
• Graphon estimation via nearest neighbor algorithm and 2D fused lasso denoising
• Nonparametric Trace Regression in High Dimensions via Sign Series Representation
• Convergence Rates of Empirical Bayes Posterior Distributions: A Variational Perspective
• Online Matrix Completion with Side Information
• Outliers Detection in Networks with Missing Links