An official website of the United States government
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
This content will become publicly available on March 13, 2026
Key-avoidance for alternating sign matrices
We initiate a systematic study of key-avoidance on alternating sign matrices (ASMs) defined via pattern-avoidance on an associated permutation called the \emph{key} of an ASM. We enumerate alternating sign matrices whose key avoids a given set of permutation patterns in several instances. We show that ASMs whose key avoids $231$ are permutations, thus any known enumeration for a set of permutation patterns including $231$ extends to ASMs. We furthermore enumerate by the Catalan numbers ASMs whose key avoids both $312$ and $321$. We also show ASMs whose key avoids $312$ are in bijection with the gapless monotone triangles of [Ayyer, Cori, Gouyou-Beauchamps 2011]. Thus key-avoidance generalizes the notion of $312$-avoidance studied there. Finally, we enumerate ASMs with a given key avoiding $312$ and $321$ using a connection to Schubert polynomials, thereby deriving an interesting Catalan identity. Comment: 28 pages
more »
« less
- Award ID(s):
- 2247089
- PAR ID:
- 10596532
- Publisher / Repository:
- Episciences
- Date Published:
- Journal Name:
- Discrete Mathematics & Theoretical Computer Science
- Volume:
- vol. 27:1, Permutation...
- Issue:
- Special issues
- ISSN:
- 1365-8050
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Plane partitions in the totally symmetric self-complementary symmetry class (TSSCPPs) are known to be equinumerous with$$n\times n$$ alternating sign matrices, but no explicit bijection is known. In this paper, we give a bijection from these plane partitions to$$\{0,1,-1\}$$ -matrices we call magog matrices, some of which are alternating sign matrices. We explore enumerative properties of these matrices related to natural statistics such as inversion number and number of negative ones. We then investigate the polytope defined as their convex hull. We show that all the magog matrices are extreme and give a partial inequality description. Finally, we define another TSSCPP polytope as the convex hull of TSSCPP boolean triangles and determine its dimension, inequalities, vertices, and facets.more » « less
-
Given a (bounded affine) permutation , we study thepositroid Catalan number defined to be the torus-equivariant Euler characteristic of the associated open positroid variety. We introduce a class ofrepetition-free permutationsand show that the corresponding positroid Catalan numbers count Dyck paths avoiding a convex subset of the rectangle. We show that any convex subset appears in this way. Conjecturally, the associated -polynomials coincide with thegeneralized -Catalan numbersthat recently appeared in relation to the shuffle conjecture, flag Hilbert schemes, and Khovanov–Rozansky homology of Coxeter links.more » « less
-
A sign pattern is an array with entries in $$\{+,-,0\}$$. A real matrix $$Q$$ is row orthogonal if $QQ^T = I$. The Strong Inner Product Property (SIPP), introduced in [B.A. Curtis and B.L. Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228-259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $$5\times n$$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.more » « less
-
Unlabeled sensing is a linear inverse problem with permuted measurements. We propose an alternating minimization (AltMin) algorithm with a suitable initialization for two widely considered permutation models: partially shuffled/k-sparse permutations and r-local/block diagonal permutations. Key to the performance of the AltMin algorithm is the initialization. For the exact unlabeled sensing problem, assuming either a Gaussian measurement matrix or a sub-Gaussian signal, we bound the initialization error in terms of the number of blocks and the number of shuffles. Experimental results show that our algorithm is fast, applicable to both permutation models, and robust to choice of measurement matrix. We also test our algorithm on several real datasets for the ‘linked linear regression’ problem and show superior performance compared to baseline methods.more » « less
