More Like this

1. Geometric approaches to matrix normalization and graph balancing

   https://doi.org/10.1017/fms.2025.10105  

   Needham, Tom; Shonkwiler, Clayton (September 2025, Forum of Mathematics, Sigma)

   Normal matrices, or matrices which commute with their adjoints, are of fundamental importance in pure and applied mathematics. In this paper, we study a natural functional on the space of square complex matrices whose global minimizers are normal matrices. We show that this functional, which we refer to as the non-normal energy, has incredibly well-behaved gradient descent dynamics: despite it being nonconvex, we show that the only critical points of the non-normal energy are the normal matrices, and that its gradient descent trajectories fix matrix spectra and preserve the subset of real matrices. We also show that, even when restricted to the subset of unit Frobenius norm matrices, the gradient flow of the non-normal energy retains many of these useful properties. This is applied to prove that low-dimensional homotopy groups of spaces of unit norm normal matrices vanish; for example, we show that the space of $$d \times d$$ complex unit norm normal matrices is simply connected for all $$d \geq 2$$. Finally, we consider the related problem of balancing a weighted directed graph – that is, readjusting its edge weights so that the weighted in-degree and out-degree are the same at each node. We adapt the non-normal energy to define another natural functional whose global minima are balanced graphs and show that gradient descent of this functional always converges to a balanced graph, while preserving graph spectra and realness of the weights. Our results were inspired by concepts from symplectic geometry and Geometric Invariant Theory, but we mostly avoid invoking this machinery and our proofs are generally self-contained. 

   more » « less
2. Polynomial control on stability, inversion and powers of matrices on simple graphs

   https://doi.org/https://doi.org/10.1016/j.jfa.2018.09.014  

   Shin, Chang Eon; Sun, Qiyu (January 2019, Journal of functional analysis)

   Spatially distributed networks of large size arise in a variety of science and engineering problems, such as wireless sensor networks and smart power grids. Most of their features can be described by properties of their state-space matrices whose entries have indices in the vertex set of a graph. In this paper, we introduce novel algebras of Beurling type that contain matrices on a connected simple graph having polynomial off-diagonal decay, and we show that they are Banach subalgebras of the space of all bounded operators on the space of all p-summable sequences. The $$\ell^p$$-stability of state-space matrices is an essential hypothesis for the robustness of spatially distributed networks. In this paper, we establish the equivalence among -stabilities of matrices in Beurling algebras for different exponents $$p$$, with quantitative analysis for the lower stability bounds. Admission of norm-control inversion plays a crucial role in some engineering practice. In this paper, we prove that matrices in Beurling subalgebras of have norm-controlled inversion and we find a norm-controlled polynomial with close to optimal degree. Polynomial estimate to powers of matrices is important for numerical implementation of spatially distributed networks. In this paper, we apply our results on norm-controlled inversion to obtain a polynomial estimate to powers of matrices in Beurling algebras. The polynomial estimate is a noncommutative extension about convolution powers of a complex function and is applicable to estimate the probability of hopping from one agent to another agent in a stationary Markov chain on a spatially distributed network. 

   more » « less
3. Convexification of Permutation-Invariant Sets and an Application to Sparse Principal Component Analysis

   https://doi.org/10.1287/moor.2021.1219  

   Kim, Jinhak; Tawarmalani, Mohit; Richard, Jean-Philippe P. (December 2021, Mathematics of Operations Research)

   We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and sign-invariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the K-support norm. Second, we characterize the convex hull of sets of matrices defined by constraining their singular values. As a consequence, we generalize an earlier result that characterizes the convex hull of rank-constrained matrices whose spectral norm is below a given threshold. Third, we derive convex and concave envelopes of various permutation-invariant nonlinear functions and their level sets over hypercubes, with congruent bounds on all variables. Finally, we develop new relaxations for the exterior product of sparse vectors. Using these relaxations for sparse PCA, we show that our relaxation closes 98% of the gap left by a classical semidefinite programming relaxation for instances where the covariance matrices are of dimension up to 50 × 50. 

   more » « less
4. Norm-based Generalization Bounds for Sparse Neural Networks

   Galanti, Tomer; Xu, Mengjia; Galanti, Liane; Poggio, Tomaso (December 2023, Advances in Neural Information Processing Systems)

   In this paper, we derive norm-based generalization bounds for sparse ReLU neural networks, including convolutional neural networks. These bounds differ from previous ones because they consider the sparse structure of the neural network architecture and the norms of the convolutional filters, rather than the norms of the (Toeplitz) matrices associated with the convolutional layers. Theoretically, we demonstrate that these bounds are significantly tighter than standard norm-based generalization bounds. Empirically, they offer relatively tight estimations of generalization for various simple classification problems. Collectively, these findings suggest that the sparsity of the underlying target function and the model’s architecture plays a crucial role in the success of deep learning. 

   more » « less
5. Upper-bounding the regularization constant for convex sparse signal reconstruction

   Gu, Renliang; Dogandzic, Aleksandar (February 2017, arXiv.org)

   Consider reconstructing a signal x by minimizing a weighted sum of a convex differentiable negative log-likelihood (NLL) (data-fidelity) term and a convex regularization term that imposes a convex-set constraint on x and enforces its sparsity using ℓ1-norm analysis regularization.We compute upper bounds on the regularization tuning constant beyond which the regularization term overwhelmingly dominates the NLL term so that the set of minimum points of the objective function does not change. Necessary and sufficient conditions for irrelevance of sparse signal regularization and a condition for the existence of finite upper bounds are established. We formulate an optimization problem for finding these bounds when the regularization term can be globally minimized by a feasible x and also develop an alternating direction method of multipliers (ADMM) type method for their computation. Simulation examples show that the derived and empirical bounds match. 

   more » « less