Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Random Matrix Theory

98 missions · 49 completed

Missions

Open49Completed49All98
🏆Completed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix IV: Sample Bound for Hutchinson's Trace EstimatorResearch Paper

Many computations need the trace of a matrix AAA that is never formed explicitly and can only be applied to vectors: the trace of a matrix function such as trace(A−1)\mathrm{trace}(A^{-1})trace(A−1) or log⁡det⁡A=trace(log⁡A)\log\det A = \mathrm{trace}(\log A)logdetA=trace(logA) in statistics and lattice QCD, the Frobenius norm ∥B∥F2=trace(BTB)\|B\|_F^2 = \mathrm{trace}(B^TB)∥B∥F2​=trace(BTB) of an operator, or the number of triangles of a graph. The…

7 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix II: Exact Rank of a Projection Matrix from the Gaussian Trace EstimatorResearch Paper

Many matrices in scientific computing are available only implicitly: one can multiply a vector by AAA, for instance by solving a linear system or applying a matrix function, but the entries of AAA are never formed. Quantities such as the trace must then be estimated from a small number of matrix–vector products. Randomized trace estimators do exactly this: draw…

7 thms3 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix I: Sample Bound for the Gaussian Trace EstimatorResearch Paper

Many computations in scientific computing, statistics and machine learning need the trace of a matrix AAA that is never formed explicitly: AAA may be f(B)f(B)f(B) for a large sparse BBB, an inverse B−1B^{-1}B−1, or a product of operators, and the only access to it is the ability to compute products AzAzAz for chosen vectors zzz. Examples are log-determinant estimation in Gaussian…

9 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

High-Dimensional Probability XI: Dvoretzky-Milman's TheoremTextbook

A striking fact discovered by Dvoretzky in the 1960s (conjectured by Grothendieck, and sharpened into its modern quantitative form by Milman in 1971) is that every high-dimensional convex body, however irregular, contains a round slice: a random low-dimensional section (or projection) of any bounded convex set in Rn\mathbb R^nRn is, with high probability, close…

9 thms3 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: iris

Rotating Walks, Derandomized Squares, and Permutation Conjugated WalksResearch Paper

An expander is a sparse graph whose random walk mixes quickly; for a ddd-regular graph on NNN vertices the quality is measured by λ(G)\lambda(G)λ(G), the largest magnitude of a non-trivial eigenvalue of the adjacency matrix. Expanders are used throughout theoretical computer science for derandomization, error-correcting codes and pseudorandom walks (Hoory–Linial–Wigders…

49 thms2 active usersReviewed
🏆Completed
Mathematical PhysicsProbability·Captain: marwahaha

All-temperature pressure for orthogonally invariant Ising spin glassesOpen Problem

An Ising spin system probes a quadratic form only on cube vertices. The source asks whether random orthogonal eigenvectors allow its pressure to be determined by the limiting eigenvalue distribution at every positive temperature. The source is OpenAI's September 2026 manuscript.

28 thms2 active usersReviewed
🏆Completed
Functional AnalysisProbability·Captain: wurtle

A finite-entropy separation of microstates and nonmicrostates free entropyResearch Paper

Free probability treats bounded self-adjoint operators X1,…,XnX_1,\dots,X_nX1​,…,Xn​ in a tracial von Neumann algebra as noncommuting random variables, and the free analogue of independence is freeness. Voiculescu introduced two candidate analogues of Shannon entropy for such tuples. The microstates free entropy χ(X)\chi(X)χ(X) measures how large the set of matrix tuples imitating…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 4: The Exponential Last Passage Time Has the Law of the Largest Sample EigenvalueResearch Paper

Random growth models and random matrices share limit laws. The first exact instance was found by Johansson (Shape fluctuations and random matrices, Comm. Math. Phys. 2000), who showed that the last passage time of a lattice model with geometric or exponential weights has the law of the largest eigenvalue of a Laguerre (complex Wishart) random matrix. Baik,…

14 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Understanding and Using Linear Programming IX: Basis Pursuit Recovers Sparse Solutions Exactly iff the Kernel Misses the CrosspolytopeTextbook

A deep-space probe sends a vector w∈Rkw\in\mathbb{R}^kw∈Rk encoded as z=Qw∈Rnz=Qw\in\mathbb{R}^nz=Qw∈Rn, and up to about 8% of the transmitted numbers may be corrupted arbitrarily. Section 8.5 of Matoušek and Gärtner's Understanding and Using Linear Programming (Springer 2007, DOI 10.1007/978-3-540-30717-4) shows that decoding reduces to finding a sparse solution of an…

7 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix V: Sample Bound for the Mixed Unit Vector Trace EstimatorResearch Paper

Many computations in numerical linear algebra, statistics and computational physics need the trace of a matrix AAA that is never formed explicitly: AAA may be an inverse, a matrix function f(B)f(B)f(B), or a product of large operators, and the only affordable access is a routine that returns AvAvAv or vTAvv^TAvvTAv for a given vector vvv. Monte Carlo trace estimators handle this…

10 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix III: Sample Bound for Normalized Rayleigh-Quotient Trace EstimatorsResearch Paper

Many computations in numerical linear algebra, statistics and computational physics need the trace of a matrix AAA that is never formed explicitly: AAA may be an inverse, a matrix function f(B)f(B)f(B), or a product of large operators, and the only affordable access is a routine that returns AvAvAv for a given vector vvv. Examples include log-determinants and the generalized…

11 thms2 active usersReviewed
🏆Completed
Machine LearningOptimizationProbability+1·Captain: mikedeng1

High-Dimensional Probability X: Exact Sparse RecoveryTextbook

Compressed sensing asks a question that looks impossible at first: can a signal x∈Rnx\in\mathbb R^nx∈Rn be reconstructed exactly from far fewer than nnn linear measurements y=Ax∈Rmy=Ax\in\mathbb R^my=Ax∈Rm, m≪nm\ll nm≪n? Classical linear algebra says no — an underdetermined system has infinitely many solutions. But if xxx is known in advance to be sparse (most of its coordinates are…

5 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

High-Dimensional Probability VII: Slepian's Inequality for Gaussian ProcessesTextbook

A Gaussian process is a family (Xt)t∈T(X_t)_{t\in T}(Xt​)t∈T​ of jointly Gaussian real random variables indexed by an arbitrary set TTT — not necessarily time. The canonical example is Xt=⟨g,t⟩X_t = \langle g, t\rangleXt​=⟨g,t⟩ for ttt ranging over a subset T⊆RnT\subseteq\mathbb R^nT⊆Rn and ggg a standard Gaussian vector in Rn\mathbb R^nRn; this single family already encodes questions as varied as the…

11 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

High-Dimensional Probability II: Concentration Inequalities for Sums of Independent Random VariablesTextbook

The central limit theorem tells us that a normalized sum of independent random variables converges in distribution to a Gaussian. For applications — bounding the failure probability of a randomized algorithm, controlling the error of a Monte Carlo estimator, proving a generalization bound in learning theory — a limiting distribution is not enough: what is…

7 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

High-Dimensional Probability I: Approximate Carathéodory's TheoremTextbook

Many arguments in high-dimensional geometry, statistics and computer science need to approximate a point of a convex set by an average of a handful of extreme points, rather than represent it exactly. The classical Carathéodory theorem (1907) answers the exact question: every point of the convex hull of a set T⊆RnT \subseteq \mathbb{R}^nT⊆Rn is a convex combination…

2 thms2 active usersReviewed
🏆Completed
Probability·Captain: Hix_Lab

Singh Theorem: cN=π215(1−4N2)c_N = \frac{\pi^2}{15}\left(1 - \frac{4}{N^2}\right)cN​=15π2​(1−N24​)Research Paper

The local statistics of eigenvalues of Haar distributed unitary matrices (the circular unitary ensemble) are a standard model for spacings of zeros of the Riemann zeta function. This mission concerns the characteristic polynomial Λ(θ)=det⁡(I−e−iθU)\Lambda(\theta) = \det(I - e^{-i\theta}U)Λ(θ)=det(I−e−iθU) at two adjacent eigenangles, and how the difference of log⁡∣Λ′∣\log|\Lambda'|log∣Λ′∣ at those two…

5 thms1 active userReviewed
🏆Completed
Numerical AnalysisProbability·Captain: tc

Gaussian Random Matrices III: Extreme Singular Values and ConcentrationTextbook

A tall N×nN\times nN×n matrix with independent standard normal entries is, with high probability, a near-isometry: all its singular values lie in [N−n, N+n][\sqrt N-\sqrt n,\ \sqrt N+\sqrt n][N​−n​, N​+n​] up to Gaussian fluctuations. This is Gordon's theorem together with Gaussian concentration (Vershynin 2012, Theorem 5.32 and Corollary 5.35), the non-asymptotic counterpart of the…

8 thms1 active userReviewed
🏆Completed
Numerical AnalysisProbability·Captain: tc

Gaussian Random Matrices I: Rotation Invariance and Moment IdentitiesTextbook

Randomized algorithms for low-rank approximation — the randomized SVD of Halko, Martinsson and Tropp (HMT 2011), generalized Nyström, randomized subspace iteration, one-pass sketching (Tropp–Webber 2023) — multiply the input matrix by a random test matrix Ω\OmegaΩ with independent standard normal entries. Every error bound for these methods rests on a small…

8 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 8: Lieb’s ConcavityTextbook

Prove Lieb’s concavity theorem (Theorem 8.1.1, also stated as Theorem 3.4.1): for fixed Hermitian H, the function A ↦ tr exp(H + log A) is concave on positive-definite matrices. This is the deterministic foundation of Chapter 3’s probabilistic argument.

12 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 4: Gaussian and Rademacher SeriesTextbook

Control the spectral norm of a matrix series with independent standard Gaussian or Rademacher coefficients. The goal is Theorem 4.1.1, including its variance identity, expected-norm estimate, and tail bound for rectangular complex matrices.

10 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 7: Intrinsic DimensionTextbook

Replace ambient matrix dimension by intrinsic dimension, the ratio of trace to spectral norm. The goal is intrinsic Matrix Bernstein (Theorem 7.3.1). Intrinsic Matrix Chernoff (Theorem 7.2.1) is a second major target within the mission.

17 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 6: Matrix BernsteinTextbook

Control the spectral norm of a sum of independent, centered, bounded rectangular random matrices. The goal is Matrix Bernstein (Theorem 6.1.1), including the variance identity and both expected-norm and tail estimates.

14 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 5: Matrix ChernoffTextbook

Bound the extreme eigenvalues of a sum of independent positive-semidefinite random matrices. The goal is the complete Matrix Chernoff theorem (Theorem 5.1.1): both expectation estimates, both tails, and the identities for the mean’s extreme eigenvalues.

8 thms1 active userReviewed
🏆Completed
Linear algebraProbability·Captain: tc

An Introduction to Matrix Concentration Inequalities Ch 3: Matrix Laplace TransformTextbook

Develop the reusable matrix Laplace-transform method behind Tropp’s concentration inequalities. The goal is Theorem 3.6.1: upper and lower tail and expectation bounds for sums of independent Hermitian random matrices, expressed through their matrix cumulant-generating functions.

8 thms1 active userReviewed
PreviousPage 2 of 2Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me