I present here a pedagogical introduction to the works by Rashel Tublin and Yan V. Fyodorov on random linear systems with quadratic constraints, using tools from Random Matrix Theory and replicas [1, 2]. These notes illustrate and complement the material presented at the Summer School organised within the Puglia Summer Trimester 2023 in Bari (Italy). Consider a system of M linear equations in N unknowns, \(\sum _{j=1}^N A_{kj}x_j=b_k\) for \(k=1,\ldots ,M\) , subject to the constraint that the solutions live on the N-sphere, \(x_1^2+\cdots + x_N^2=N\) . Assume that both the coefficients \(A_{ij}\) and the parameters \(b_i\) be independent Gaussian random variables with zero mean. Using two different approaches—based on Random Matrix Theory and on a replica calculation—it is possible to compute whether a large linear system subject to a quadratic constraint is typically solvable or not, as a function of the ratio \(\alpha =M/N\) and the variance \(\sigma ^2\) of the \(b_i\) ’s. This is done by defining a quadratic loss function \(H({\boldsymbol{x}})=\frac{1}{2}\sum _{k=1}^M\left[ \sum _{j=1}^NA_{kj} x_j-b_k\right] ^2\) and computing the statistics of its minimal value on the sphere, \(\mathcal{E}_{min}=\min _{||\boldsymbol{x}||^2=N}H({\boldsymbol{x}})\) , which is zero if the system is compatible, and larger than zero if it is incompatible. One finds that there exists a compatibility threshold \(0<\alpha _c<1\) , such that systems with \(\alpha >\alpha _c\) are typically incompatible. This means that even weakly under-complete linear systems could become typically incompatible if forced to additionally obey a quadratic constraint.

Random Linear Systems with Quadratic Constraints: from Random Matrix Theory to Replicas and Back

章节
发表日期：

2025年

查看全文

Pierpaolo Vivo

摘要

I present here a pedagogical introduction to the works by Rashel Tublin and Yan V. Fyodorov on random linear systems with quadratic constraints, using tools from Random Matrix Theory and replicas [1, 2]. These notes illustrate and complement the material presented at the Summer School organised within the Puglia Summer Trimester 2023 in Bari (Italy). Consider a system of M linear equations in N unknowns, \(\sum _{j=1}^N A_{kj}x_j=b_k\) for \(k=1,\ldots ,M\) , subject to the constraint that the solutions live on the N-sphere, \(x_1^2+\cdots + x_N^2=N\) . Assume that both the coefficients \(A_{ij}\) and the parameters \(b_i\) be independent Gaussian random variables with zero mean. Using two different approaches—based on Random Matrix Theory and on a replica calculation—it is possible to compute whether a large linear system subject to a quadratic constraint is typically solvable or not, as a function of the ratio \(\alpha =M/N\) and the variance \(\sigma ^2\) of the \(b_i\) ’s. This is done by defining a quadratic loss function \(H({\boldsymbol{x}})=\frac{1}{2}\sum _{k=1}^M\left[ \sum _{j=1}^NA_{kj} x_j-b_k\right] ^2\) and computing the statistics of its minimal value on the sphere, \(\mathcal{E}_{min}=\min _{||\boldsymbol{x}||^2=N}H({\boldsymbol{x}})\) , which is zero if the system is compatible, and larger than zero if it is incompatible. One finds that there exists a compatibility threshold \(0<\alpha _c<1\) , such that systems with \(\alpha >\alpha _c\) are typically incompatible. This means that even weakly under-complete linear systems could become typically incompatible if forced to additionally obey a quadratic constraint.