Finding a large submatrix of a Gaussian random matrix

Finding a large submatrix of a Gaussian random matrix

We consider the problem of finding a k × k submatrix of an n × n matrix with i.i.d. standard Gaussian entries, which has a large average entry. It was shown in [Bhamidi, Dey and Nobel (2012)] using nonconstructive methods that the largest average value of a k × k submatrix is 2(1 + o(1))√log n/k, wi...

书目详细资料
Main Authors:	Gamarnik, David, Li, Quan
其他作者:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
格式:	文件
出版:	Institute of Mathematical Statistics 2019
在线阅读:	http://hdl.handle.net/1721.1/120593 https://orcid.org/0000-0001-8898-8778 https://orcid.org/0000-0002-3726-1517

相似书籍

The overlap gap property in principal submatrix recovery
由: Gamarnik, David
出版: (2021)

The overlap gap property in principal submatrix recovery
由: Gamarnik, David
出版: (2021)

The overlap gap property in principal submatrix recovery
由: Gamarnik, David, et al.
出版: (2022)

A Solution Matrix by IEVP under the Central Principle Submatrix Constraints
由: Vineet Bhatt, et al.
出版: (2024-01-01)

An Iterative Method for the Least-Squares Problems of a General Matrix Equation Subjects to Submatrix Constraints
由: Li-fang Dai, et al.
出版: (2013-01-01)

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
由: Scott, A, et al.
出版: (2023)

Locally structured low-rank MR image reconstruction using submatrix constraints
由: Chen, X, et al.
出版: (2022)

On the max-cut of sparse random graphs
由: Gamarnik, David, et al.
出版: (2019)

Boosting determinant quantum Monte Carlo with submatrix updates: Unveiling the phase diagram of the 3D Hubbard model
由: Fanjie Sun, Xiao Yan Xu
出版: (2025-02-01)

Statistical properties of eigenvectors in non-Hermitian Gaussian random matrix ensembles
由: Mehlig, B, et al.
出版: (1999)

A Note on Alternating Minimization Algorithm for the Matrix Completion Problem
由: Gamarnik, David, et al.
出版: (2017)

A simple derivation of the Tracy-Widom distribution of the maximal eigenvalue of a Gaussian unitary random matrix
由: Nadal, C, et al.
出版: (2011)

Gaussian random processes /
由: Ibragimov, Il'dar Abdulovich, et al.
出版: (1978)

A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
由: Gamarnik, David, et al.
出版: (2017)

The overlap gap property: A topological barrier to optimizing over random structures
由: Gamarnik, David
出版: (2022)

Right-convergence of sparse random graphs
由: Gamarnik, David
出版: (2014)

Optimization of Gaussian Random Fields
由: Dow, Eric, et al.
出版: (2015)

Smooth random functions, random ODEs, and Gaussian processes
由: Filip, S, et al.
出版: (2019)

GAUSSIAN RANDOM-FIELDS IN SPHERICAL COORDINATES
由: Binney, J, et al.
出版: (1991)

Matched filter decoding of random binary and Gaussian codes in broadband Gaussian channel
由: Abdrashitov, Vitaly, et al.
出版: (2014)

Limits of local algorithms over sparse random graphs
由: Gamarnik, David, et al.
出版: (2014)

Giant Component in Random Multipartite Graphs with given Degree Sequences
由: Gamarnik, David, et al.
出版: (2019)

Polar Functions for Anisotropic Gaussian Random Fields
由: Zhenlong Chen
出版: (2014-01-01)

Performance of Sequential Local Algorithms for the Random NAE-$K$-SAT Problem
由: Gamarnik, David, et al.
出版: (2017)

A random decay non-gaussian time series model /
由: 407549 Sim, Chiaw Hock
出版: (1983)

Finding cliques using few probes
由: Feige, Uriel, et al.
出版: (2021)

Correlation Decay in Random Decision Networks
由: Gamarnik, David, et al.
出版: (2019)

Parallel Gaussian Process Regression with Low-Rank Covariance Matrix Approximations
由: Chen, Jie, et al.
出版: (2014)

Network inference in matrix-variate Gaussian models with non-independent noise
由: Dahl, A, et al.
出版: (2013)

Large-scale heteroscedastic regression via Gaussian process
由: Liu, Haitao, et al.
出版: (2022)

Non-Gaussianity from Large-Scale Structure Surveys
由: Licia Verde
出版: (2010-01-01)

Primordial Non-Gaussianity in the Large-Scale Structure of the Universe
由: Vincent Desjacques, et al.
出版: (2010-01-01)

On the Shaker Simulation of Wind-Induced Non-Gaussian Random Vibration
由: Fei Xu, et al.
出版: (2016-01-01)

Extreme value statistics of smooth Gaussian random fields
由: Colombi, S, et al.
出版: (2011)

Extreme value statistics of smooth random Gaussian fields
由: Colombi, S, et al.
出版: (2011)

Gaussian Markov random field spatial models in GAMLSS
由: De Bastiani, Fernanda, et al.
出版: (2016)

On the justification of Gaussian heuristic method in the theory of random vibration
由: Nguyen Cao Menh
出版: (1979-12-01)

Wave propagation in random media: beyond Gaussian statistics
由: Garnier Josselin
出版: (2023-01-01)

Sharp convergence of nonlinear functionals of a class of Gaussian random fields
由: Xu, W
出版: (2018)

An Improvement of Computing Newton’s Direction for Finding Unconstrained Minimizer for Large-Scale Problems with an Arrowhead Hessian Matrix
由: Khadizah Ghazali, et al.
出版: (2020)