On the maximal size of large-average and ANOVA-fit submatrices in a Gaussian random matrix.

We investigate the maximal size of distinguished submatrices of a Gaussian random matrix. Of interest are submatrices whose entries have an average greater than or equal to a positive constant, and submatrices whose entries are well fit by a two-way ANOVA model. We identify size thresholds and associated (asymptotic) probability bounds for both large-average and ANOVA-fit submatrices. Probability bounds are obtained when the matrix and submatrices of interest are square and, in rectangular cases, when the matrix and submatrices of interest have fixed aspect ratios. Our principal result is an almost sure interval concentration result for the size of large average submatrices in the square case.

• Publication year

  2010

• Venue

  Bernoulli

• Publication date

  2010-09-03

• Fields of study

  Mathematics, Medicine

• Identifiers
  DOI 10.3150/11-BEJ394arXiv 1009.0562PMID 24194673PMCID PMC3816128
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Author Manuscript

  2013cited by this paper
• An Introduction to Random Matrices

  2009cited by this paper
• Finding large average submatrices in high dimensional data

  2009influential reference
• On the size and recovery of submatrices of ones in a random binary matrix

  2008influential reference
• ASYMPTOTICS OF SAMPLE EIGENSTRUCTURE FOR A LARGE DIMENSIONAL SPIKED COVARIANCE MODEL

  2007cited by this paper
• Significance and Recovery of Block Structures in Binary Matrices with Noise

  2006cited by this paper
• Molecular portraits and 70-gene prognosis signature are preserved throughout the metastatic process of breast cancer.

  2005cited by this paper
• Approximating the cut-norm via Grothendieck's inequality

  2004cited by this paper
• Cluster analysis for gene expression data: a survey

  2004cited by this paper
• Biclustering gene-feature matrices for statistically significant dense patterns

  2004cited by this paper
• Subspace clustering for high dimensional data: a review

  2004cited by this paper
• Repeated observation of breast tumor subtypes in independent gene expression data sets

  2003cited by this paper
• Discovering statistically significant biclusters in gene expression data

  2002cited by this paper
• Gene expression patterns of breast carcinomas distinguish tumor subclasses with clinical implications

  2001cited by this paper
• Diversity of gene expression in adenocarcinoma of the lung

  2001cited by this paper
• On Bipartite and Multipartite Clique Problems

  2001cited by this paper
• Biclustering of Expression Data

  2000cited by this paper
• Plaid models for gene expression data

  2000cited by this paper
• Molecular portraits of human breast tumours

  2000cited by this paper
• Molecular classification of cancer: class discovery and class prediction by gene expression monitoring.

  1999cited by this paper
• Poisson Approximation and the Chen-Stein Method

  1990influential reference
• Matrix analysis

  1985influential reference
• A Limit Theorem for the Norm of Random Matrices

  1980cited by this paper
• Cliques in random graphs

  1976cited by this paper
• The one-sided barrier problem for Gaussian noise

  1962cited by this paper
• The Analysis of Variance

  1960cited by this paper
• Ieee/acm Transactions on Computational Biology and Bioinformatics 1 Biclustering Algorithms for Biological Data Analysis: a Survey

  year unknowncited by this paper
• : Studies

  year unknowncited by this paper

• Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers

  2025cites this paper
• Statistical mechanics of the maximum-average submatrix problem

  2023cites this paper
• Detection and Recovery of Hidden Submatrices

  2023cites this paper
• Principal minors of Gaussian orthogonal ensemble

  2022cites this paper
• Lattice partition recovery with dyadic CART

  2021cites this paper
• Tensor Clustering with Planted Structures: Statistical Optimality and Computational Limits

  2020cites this paper
• Connection Between the Selection Problem for a Sparse Submatrix of a Large-Size Matrix and the Bayesian Problem of Hypotheses Testing

  2020cites this paper
• Connection Between the Selection Problem for a Sparse Submatrix of a Large-Size Matrix and the Bayesian Problem of Hypotheses Testing

  2020cites this paper
• Feeling the Bern: Adaptive Estimators for Bernoulli Probabilities of Pairwise Comparisons

  2019cites this paper
• Phase transition for eigenvalues and recovery of rank one matrices

  2019cites this paper
• ST ] 1 3 Ju l 2 01 8 Submitted to the Annals of Statistics OPTIMALITY AND SUB-OPTIMALITY OF PCA I : SPIKED RANDOM MATRIX MODELS By

  2018cites this paper
• A loop-counting method for covariate-corrected low-rank biclustering of gene-expression and genome-wide association study data

  2018cites this paper
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models

  2018cites this paper
• Energy landscape for large average submatrix detection problems in Gaussian random matrices

  2017cites this paper
• Lectures on Combinatorial Statistics

  2017cites this paper
• Optimality and Sub-optimality of PCA for Spiked Random Matrices and Synchronization

  2016cites this paper
• On the Statistical Limits of Convex Relaxations

  2016cites this paper
• Finding a large submatrix of a Gaussian random matrix

  2016cites this paper
• Volume Ratio, Sparsity, and Minimaxity Under Unitarily Invariant Norms

  2015cites this paper
• A systematic evaluation of high-dimensional, ensemble-based regression for exploring large model spaces in microbiome analyses

  2015cites this paper
• Rate Optimal Denoising of Simultaneously Sparse and Low Rank Matrices

  2014cites this paper
• Non-Negative Principal Component Analysis: Message Passing Algorithms and Sharp Asymptotics

  2014cites this paper
• Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

  2014cites this paper
• Sharp detection of smooth signals in a high-dimensional sparse matrix with indirect observations

  2013influential citation
• Sharp Variable Selection of a Sparse Submatrix in a High-Dimensional Noisy Matrix

  2013influential citation
• Computational Barriers in Minimax Submatrix Detection

  2013cites this paper
• Computational Lower Bounds for Sparse PCA

  2013cites this paper
• Volume ratio, sparsity, and minimaxity under unitarily invariant norms

  2013cites this paper
• Complexity Theoretic Lower Bounds for Sparse Principal Component Detection

  2013cites this paper
• Recovering block-structured activations using compressive measurements

  2012cites this paper
• Energy landscape for large average submatrix detection problems in Gaussian random matrices

  2012cites this paper
• HIGH DIMENSIONAL SPARSE COVARIANCE ESTIMATION : ACCURATE THRESHOLDS FOR THE MAXIMAL DIAGONAL ENTRY AND FOR THE LARGEST CORRELATION COEFFICIENT

  2012cites this paper
• Optimal detection of sparse principal components in high dimension

  2012cites this paper
• Finding and Leveraging Structure in Learning Problems

  2012cites this paper
• Optimal detection of sparse principal components in high

  2012cites this paper
• Statistical and computational tradeoffs in biclustering

  2011cites this paper
• Minimax Localization of Structural Information in Large Noisy Matrices

  2011cites this paper
• Detection of a sparse submatrix of a high-dimensional noisy matrix

  2011cites this paper