More Like this

1. Explicit Polynomial Sequences with Maximal Spaces of Partial Derivatives and a Question of K. Mulmuley

   https://doi.org/10.4086/toc.2019.v015a003  

   Gesmundo, Fulvio ; Landsberg, Joseph M. ( January 2019 , Theory of Computing)

   null (Ed.)

   We answer a question of K. Mulmuley. Efremenko et al. (Math. Comp., 2018) have shown that the method of shifted partial derivatives cannot be used to separate the padded permanent from the determinant. Mulmuley asked if this “no-go” result could be extended to a model without padding. We prove this is indeed the case using the iterated matrix multiplication polynomial. We also provide several examples of polynomials with maximal space of partial derivatives, including the complete symmetric polynomials. We apply Koszul flattenings to these polynomials to have the first explicit sequence of polynomials with symmetric border rank lower bounds higher than the bounds attainable via partial derivatives. 

   more » « less
2. Boolean Product Polynomials, Schur Positivity, and Chern Plethysm

   https://doi.org/10.1093/imrn/rnz261  

   Billey, Sara C. ; Rhoades, Brendon ; Tewari, Vasu ( November 2019 , International Mathematics Research Notices)

   Let $k \leq n$ be positive integers, and let $X_n = (x_1, \dots , x_n)$ be a list of $n$ variables. The Boolean product polynomial$B_{n,k}(X_n)$ is the product of the linear forms $\sum _{i \in S} x_i$, where $S$ ranges over all $k$-element subsets of $\{1, 2, \dots , n\}$. We prove that Boolean product polynomials are Schur positive. We do this via a new method of proving Schur positivity using vector bundles and a symmetric function operation we call Chern plethysm. This gives a geometric method for producing a vast array of Schur positive polynomials whose Schur positivity lacks (at present) a combinatorial or representation theoretic proof. We relate the polynomials $B_{n,k}(X_n)$ for certain $k$ to other combinatorial objects including derangements, positroids, alternating sign matrices, and reverse flagged fillings of a partition shape. We also relate $B_{n,n-1}(X_n)$ to a bigraded action of the symmetric group ${\mathfrak{S}}_n$ on a divergence free quotient of superspace.

    

   more » « less
3. On the Cartan decomposition for classical random matrix ensembles

   https://doi.org/10.1063/5.0087010  

   Edelman, Alan ; Jeong, Sungwoo ( June 2022 , Journal of Mathematical Physics)

   We complete Dyson’s dream by cementing the links between symmetric spaces and classical random matrix ensembles. Previous work has focused on a one-to-one correspondence between symmetric spaces and many but not all of the classical random matrix ensembles. This work shows that we can completely capture all of the classical random matrix ensembles from Cartan’s symmetric spaces through the use of alternative coordinate systems. In the end, we have to let go of the notion of a one-to-one correspondence. We emphasize that the KAK decomposition traditionally favored by mathematicians is merely one coordinate system on the symmetric space, albeit a beautiful one. However, other matrix factorizations, especially the generalized singular value decomposition from numerical linear algebra, reveal themselves to be perfectly valid coordinate systems that one symmetric space can lead to many classical random matrix theories. We establish the connection between this numerical linear algebra viewpoint and the theory of generalized Cartan decompositions. This, in turn, allows us to produce yet more random matrix theories from a single symmetric space. Yet, again, these random matrix theories arise from matrix factorizations, though ones that we are not aware have appeared in the literature. 

   more » « less
4. Extensions of polynomial plank covering theorems

   https://doi.org/10.1112/blms.12979  

   Glazyrin, Alexey ; Karasev, Roman ; Polyanskii, Alexander ( December 2023 , Bulletin of the London Mathematical Society)

   We prove a complex polynomial plank covering theorem for not necessarily homogeneous polynomials. As the consequence of this result, we extend the complex plank theorem of Ball to the case of planks that are not necessarily centrally symmetric and not necessarily round. We also prove a weaker version of the spherical polynomial plank covering conjecture for planks of different widths.

    

   more » « less
5. Implicit Balancing and Regularization: Generalization and Convergence Guarantees for Overparameterized Asymmetric Matrix Sensing

   Soltanolkotabi, Mahdi ; Stöger, Dominik ; Xie, Changzhi ( July 2023 , Proceedings of Thirty Sixth Conference on Learning Theory)

   Recently, there has been significant progress in understanding the convergence and generalization properties of gradient-based methods for training overparameterized learning models. However, many aspects including the role of small random initialization and how the various parameters of the model are coupled during gradient-based updates to facilitate good generalization, remain largely mysterious. A series of recent papers have begun to study this role for non-convex formulations of symmetric Positive Semi-Definite (PSD) matrix sensing problems which involve reconstructing a low-rank PSD matrix from a few linear measurements. The underlying symmetry/PSDness is crucial to existing convergence and generalization guarantees for this problem. In this paper, we study a general overparameterized low-rank matrix sensing problem where one wishes to reconstruct an asymmetric rectangular low-rank matrix from a few linear measurements. We prove that an overparameterized model trained via factorized gradient descent converges to the low-rank matrix generating the measurements. We show that in this setting, factorized gradient descent enjoys two implicit properties: (1) coupling of the trajectory of gradient descent where the factors are coupled in various ways throughout the gradient update trajectory and (2) an algorithmic regularization property where the iterates show a propensity towards low-rank models despite the overparameterized nature of the factorized model. These two implicit properties in turn allow us to show that the gradient descent trajectory from small random initialization moves towards solutions that are both globally optimal and generalize well. 

   more » « less