Search

The g-convexity of functions on manifolds is a generalization of the convexity of functions on Rn. It plays an essential role in both differential geometry and non-convex optimization theory. This paper is concerned with g-convex smooth functions on manifolds. We establish criteria for the existence of a Riemannian metric (or connection) with respect to which a given function is g-convex. Using these criteria, we obtain three sparseness results for g-convex functions: (1) The set of g-convex functions on a compact manifold is nowhere dense in the space of smooth functions. (2) Most polynomials on Rn that is g-convex with respect to some geodesically complete connection has at most one critical point. (3) The density of g-convex univariate (resp. quadratic, monomial, additively separable) polynomials asymptotically decreases to zero

This paper studies the stability of tensor ranks under field extensions. Our main contributions are fourfold: (1) We prove that the analytic rank is stable under field extensions. (2) We establish the equivalence between the partition rank vs. analytic rank conjecture and the stability conjecture for partition rank. We also prove that they are equivalent to other two important conjectures. (3) We resolve the Adiprasito-Kazhdan-Ziegler conjecture on the stability of the slice rank of linear subspaces under field extensions. (4) As an application of (1), we show that the geometric rank is equal to the analytic rank up to a constant factor., Comment: 18 pages

Significant progress has been made in the field of Instruction-based Image Editing (IIE). However, evaluating these models poses a significant challenge. A crucial requirement in this field is the establishment of a comprehensive evaluation benchmark for accurately assessing editing results and providing valuable insights for its further development. In response to this need, we propose I2EBench, a comprehensive benchmark designed to automatically evaluate the quality of edited images produced by IIE models from multiple dimensions. I2EBench consists of 2,000+ images for editing, along with 4,000+ corresponding original and diverse instructions. It offers three distinctive characteristics: 1) Comprehensive Evaluation Dimensions: I2EBench comprises 16 evaluation dimensions that cover both high-level and low-level aspects, providing a comprehensive assessment of each IIE model. 2) Human Perception Alignment: To ensure the alignment of our benchmark with human perception, we conducted an extensive user study for each evaluation dimension. 3) Valuable Research Insights: By analyzing the advantages and disadvantages of existing IIE models across the 16 dimensions, we offer valuable research insights to guide future development in the field. We will open-source I2EBench, including all instructions, input images, human annotations, edited images from all evaluated methods, and a simple script for evaluating the results from new IIE models. The code, dataset and generated images from all IIE models are provided in github: https://github.com/cocoshe/I2EBench., Comment: NeurIPS2024, 15 pages, 7 figures

This paper is concerned with rational curves on real classical groups. Our contributions are three-fold: (i) We determine the structure of quadratic rational curves on real classical groups. As a consequence, we completely classify quadratic rational curves on $\mathrm{U}_n$, $\mathrm{O}_n(\mathbb{R})$, $\mathrm{O}_{n-1,1}(\mathbb{R})$ and $\mathrm{O}_{n-2,2}(\mathbb{R})$. (ii) We prove a decomposition theorem for rational curves on real classical groups, which can be regarded as a non-commutative generalization of the fundamental theorem of algebra and partial fraction decomposition. (iii) As an application of (i) and (ii), we generalize Kempe's Universality Theorem to rational curves on homogeneous spaces., Comment: 50 pages

We present foundation language models developed to power Apple Intelligence features, including a ~3 billion parameter model designed to run efficiently on devices and a large server-based language model designed for Private Cloud Compute. These models are designed to perform a wide range of tasks efficiently, accurately, and responsibly. This report describes the model architecture, the data used to train the model, the training process, how the models are optimized for inference, and the evaluation results. We highlight our focus on Responsible AI and how the principles are applied throughout the model development.

We derive three families of orthogonally-equivariant matrix submanifold models for the Grassmann, flag, and Stiefel manifolds respectively. These families are exhaustive -- every orthogonally-equivariant submanifold model of the lowest dimension for any of these manifolds is necessarily a member of the respective family, with a small number of exceptions. They have several computationally desirable features. The orthogonal equivariance allows one to obtain, for various differential geometric objects and operations, closed-form analytic expressions that are readily computable with standard numerical linear algebra. The minimal dimension aspect translates directly to a speed advantage in computations. And having an exhaustive list of all possible matrix models permits one to identify the model with the lowest matrix condition number, which translates to an accuracy advantage in computations. As an interesting aside, we will see that the family of models for the Stiefel manifold is naturally parameterized by the Cartan manifold, i.e., the positive definite cone equipped with its natural Riemannian metric., Comment: 17 pages

We show that the flag manifold $\operatorname{Flag}(k_1,\dots, k_p, \mathbb{R}^n)$, with Grassmannian the special case $p=1$, has an $\operatorname{SO}_n(\mathbb{R})$-equivariant embedding in an Euclidean space of dimension $(n-1)(n+2)/2$, two orders of magnitude below the current best known result. We will show that the value $(n-1)(n+2)/2$ is the smallest possible and that any $\operatorname{SO}_n(\mathbb{R})$-equivariant embedding of $\operatorname{Flag}(k_1,\dots, k_p, \mathbb{R}^n)$ in an ambient space of minimal dimension is equivariantly equivalent to the aforementioned one., Comment: 11 pages

We show that unconstrained quadratic optimization over a Grassmannian $\operatorname{Gr}(k,n)$ is NP-hard. Our results cover all scenarios: (i) when $k$ and $n$ are both allowed to grow; (ii) when $k$ is arbitrary but fixed; (iii) when $k$ is fixed at its lowest possible value $1$. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold $\operatorname{V}(k,n)$ and the orthogonal group $\operatorname{O}(n)$. As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone $\mathbb{S}^n_{\scriptscriptstyle++}$ regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of $\mathrm{FPTAS}$ in all cases., Comment: 19 pages

We show that modeling a Grassmannian as symmetric orthogonal matrices $\operatorname{Gr}(k,\mathbb{R}^n) \cong\{Q \in \mathbb{R}^{n \times n} : Q^{\scriptscriptstyle\mathsf{T}} Q = I, \; Q^{\scriptscriptstyle\mathsf{T}} = Q,\; \operatorname{tr}(Q)=2k - n\}$ yields exceedingly simple matrix formulas for various curvatures and curvature-related quantities, both intrinsic and extrinsic. These include Riemann, Ricci, Jacobi, sectional, scalar, mean, principal, and Gaussian curvatures; Schouten, Weyl, Cotton, Bach, Pleba\'nski, cocurvature, nonmetricity, and torsion tensors; first, second, and third fundamental forms; Gauss and Weingarten maps; and upper and lower delta invariants. We will derive explicit, simple expressions for the aforementioned quantities in terms of standard matrix operations that are stably computable with numerical linear algebra. Many of these aforementioned quantities have never before been presented for the Grassmannian., Comment: 25 pages

The degree of the Grassmannian with respect to the Pl\"ucker embedding is well-known. However, the Pl\"ucker embedding, while ubiquitous in pure mathematics, is almost never used in applied mathematics. In applied mathematics, the Grassmannian is usually embedded as projection matrices $\operatorname{Gr}(k,\mathbb{R}^n) \cong \{P \in \mathbb{R}^{n \times n} : P^{\scriptscriptstyle\mathsf{T}} = P = P^2,\; \operatorname{tr}(P) = k\}$ or as involution matrices $\operatorname{Gr}(k,\mathbb{R}^n) \cong \{X \in \mathbb{R}^{n \times n} : X^{\scriptscriptstyle\mathsf{T}} = X,\; X^2 = I,\; \operatorname{tr}(X)=2k - n\}$. We will determine an explicit expression for the degree of the Grassmannian with respect to these embeddings. In so doing, we resolved a conjecture of Devriendt--Friedman--Sturmfels about the degree $\operatorname{Gr}(2, \mathbb{R}^n)$ and in fact generalized it to $\operatorname{Gr}(k, \mathbb{R}^n)$. We also proved a set theoretic variant of another conjecture of Devriendt--Friedman--Sturmfels about the limit of $\operatorname{Gr}(k,\mathbb{R}^n)$ in the sense of Gr\"obner degneration., Comment: 16 pages

We establish a lower bound for the complexity of multiplying two skew polynomials. The lower bound coincides with the upper bound conjectured by Caruso and Borgne in 2017, up to a log factor. We present algorithms for three special cases, indicating that the aforementioned lower bound is quasi-optimal. In fact, our lower bound is quasi-optimal in the sense of bilinear complexity. In addition, we discuss the average bilinear complexity of simultaneous multiplication of skew polynomials and the complexity of skew polynomial multiplication in the case of towers of extensions.

Pre-training large language models is known to be extremely resource intensive and often times inefficient, under-utilizing the information encapsulated in the training text sequences. In this paper, we present SpacTor, a new training procedure consisting of (1) a hybrid objective combining span corruption (SC) and token replacement detection (RTD), and (2) a two-stage curriculum that optimizes the hybrid objective over the initial $\tau$ iterations, then transitions to standard SC loss. We show empirically that the effectiveness of the hybrid objective is tied to the two-stage pre-training schedule, and provide extensive analysis on why this is the case. In our experiments with encoder-decoder architectures (T5) on a variety of NLP tasks, SpacTor-T5 yields the same downstream performance as standard SC pre-training, while enabling a 50% reduction in pre-training iterations and 40% reduction in total FLOPs. Alternatively, given the same amount of computing budget, we find that SpacTor results in significantly improved downstream benchmark performance., Comment: 9+13 pages, 5 figures

Positive semidefinite (PSD) matrices are indispensable in many fields of science. A similarity measurement for such matrices is usually an essential ingredient in the mathematical modelling of a scientific problem. This paper proposes a unified framework to construct similarity measurements for PSD matrices. The framework is obtained by exploring the fiber bundle structure of the cone of PSD matrices and generalizing the idea of the point-set distance previously developed for linear subsapces and positive definite (PD) matrices. The framework demonstrates both theoretical advantages and computational convenience: (1) We prove that the similarity measurement constructed by the framework can be recognized either as the cost of a parallel transport or as the length of a quasi-geodesic curve. (2) We extend commonly used divergences for equidimensional PD matrices to the non-equidimensional case. Examples include Kullback-Leibler divergence, Bhattacharyya divergence and R\'enyi divergence. We prove that these extensions enjoy the same consistency property as their counterpart for geodesic distance. (3) We apply our geometric framework to further extend those in (2) to similarity measurements for arbitrary PSD matrices. We also provide simple formulae to compute these similarity measurements in most situations.

This report introduces a new family of multimodal models, Gemini, that exhibit remarkable capabilities across image, audio, video, and text understanding. The Gemini family consists of Ultra, Pro, and Nano sizes, suitable for applications ranging from complex reasoning tasks to on-device memory-constrained use-cases. Evaluation on a broad range of benchmarks shows that our most-capable Gemini Ultra model advances the state of the art in 30 of 32 of these benchmarks - notably being the first model to achieve human-expert performance on the well-studied exam benchmark MMLU, and improving the state of the art in every one of the 20 multimodal benchmarks we examined. We believe that the new capabilities of the Gemini family in cross-modal reasoning and language understanding will enable a wide variety of use cases. We discuss our approach toward post-training and deploying Gemini models responsibly to users through services including Gemini, Gemini Advanced, Google AI Studio, and Cloud Vertex AI.

Motion forecasting plays a crucial role in autonomous driving, with the aim of predicting the future reasonable motions of traffic agents. Most existing methods mainly model the historical interactions between agents and the environment, and predict multi-modal trajectories in a feedforward process, ignoring potential trajectory changes caused by future interactions between agents. In this paper, we propose a novel Future Feedback Interaction Network (FFINet) to aggregate features the current observations and potential future interactions for trajectory prediction. Firstly, we employ different spatial-temporal encoders to embed the decomposed position vectors and the current position of each scene, providing rich features for the subsequent cross-temporal aggregation. Secondly, the relative interaction and cross-temporal aggregation strategies are sequentially adopted to integrate features in the current fusion module, observation interaction module, future feedback module and global fusion module, in which the future feedback module can enable the understanding of pre-action by feeding the influence of preview information to feedforward prediction. Thirdly, the comprehensive interaction features are further fed into final predictor to generate the joint predicted trajectories of multiple agents. Extensive experimental results show that our FFINet achieves the state-of-the-art performance on Argoverse 1 and Argoverse 2 motion forecasting benchmarks., Comment: 11 pages, 8 figures, 12 tables

In this paper we derive and analyze an algorithm for inverting quaternion matrices. The algorithm is an analogue of the Frobenius algorithm for the complex matrix inversion. On the theory side, we prove that our algorithm is more efficient that other existing methods. Moreover, our algorithm is optimal in the sense of the least number of complex inversions. On the practice side, our algorithm outperforms existing algorithms on randomly generated matrices. We argue that this algorithm can be used to improve the practical utility of recursive Strassen-type algorithms by providing the fastest possible base case for the recursive decomposition process when applied to quaternion matrices.

The problem of computing the optimum of a function on a finite set is an important problem in mathematics and computer science. Many combinatorial problems such as MAX-SAT and MAXCUT can be recognized as optimization problems on the hypercube $C_2^n = \{-1,1\}^n$ consisting of $2^n$ points. It has been noticed that if a finite set is equipped with an abelian group structure, then one can efficiently certify nonnegative functions on it by Fourier sum of squares (FSOS). Motivated by these works, this paper is devoted to developing a framework to find a lower bound of a function on a finite abelian group efficiently. We implement our algorithm by the SDP solver SDPNAL+ for computing the verified lower bound of $f$ on $G$ and test it on the MAX-2SAT and MAX-3SAT benchmark problems from the Max-SAT competitions in 2009 and 2016. Beyond that, we also test our algorithm on random functions on $C_3^n$. These experiments demonstrate the advantage of our algorithm over previously known methods.

We study the geometry of flag manifolds under different embeddings into a product of Grassmannians. We show that differential geometric objects and operations -- tangent vector, metric, normal vector, exponential map, geodesic, parallel transport, gradient, Hessian, etc -- have closed-form analytic expressions that are computable with standard numerical linear algebra. Furthermore, we are able to derive a coordinate descent method in the flag manifold that performs well compared to other gradient descent methods., Comment: 26 pages

This paper studies the curious phenomenon for machine learning models with Transformer architectures that their activation maps are sparse. By activation map we refer to the intermediate output of the multi-layer perceptrons (MLPs) after a ReLU activation function, and by sparse we mean that on average very few entries (e.g., 3.0% for T5-Base and 6.3% for ViT-B16) are nonzero for each input to MLP. Moreover, larger Transformers with more layers and wider MLP hidden dimensions are sparser as measured by the percentage of nonzero entries. Through extensive experiments we demonstrate that the emergence of sparsity is a prevalent phenomenon that occurs for both natural language processing and vision tasks, on both training and evaluation data, for Transformers of various configurations, at layers of all depth levels, as well as for other architectures including MLP-mixers and 2-layer MLPs. We show that sparsity also emerges using training datasets with random labels, or with random inputs, or with infinite amount of data, demonstrating that sparsity is not a result of a specific family of datasets. We discuss how sparsity immediately implies a way to significantly reduce the FLOP count and improve efficiency for Transformers. Moreover, we demonstrate perhaps surprisingly that enforcing an even sparser activation via Top-k thresholding with a small value of k brings a collection of desired but missing properties for Transformers, namely less sensitivity to noisy training data, more robustness to input corruptions, and better calibration for their prediction confidence., Comment: A short version was presented at ICLR 2023. Previous title: Large Models are Parsimonious Learners: Activation Sparsity in Trained Transformers

We study the inversion analog of the well-known Gauss algorithm for multiplying complex matrices. A simple version is $(A + iB)^{-1} = (A + BA^{-1}B)^{-1} - i A^{-1}B(A+BA^{-1} B)^{-1}$ when $A$ is invertible, which may be traced back to Frobenius but has received scant attention. We prove that it is optimal, requiring fewest matrix multiplications and inversions over the base field, and we extend it in three ways: (i) to any invertible $A + iB$ without requiring $A$ or $B$ be invertible; (ii) to any iterated quadratic extension fields, with $\mathbb{C}$ over $\mathbb{R}$ a special case; (iii) to Hermitian positive definite matrices $A + iB$ by exploiting symmetric positive definiteness of $A$ and $A + BA^{-1}B$. We call all such algorithms Frobenius inversions, which we will see do not follow from Sherman--Morrison--Woodbury type identities and cannot be extended to Moore--Penrose pseudoinverse. We show that a complex matrix with well-conditioned real and imaginary parts can be arbitrarily ill-conditioned, a situation tailor-made for Frobenius inversion. We prove that Frobenius inversion for complex matrices is faster than standard inversion by LU decomposition and Frobenius inversion for Hermitian positive definite matrices is faster than standard inversion by Cholesky decomposition. We provide extensive numerical experiments, applying Frobenius inversion to solve linear systems, evaluate matrix sign function, solve Sylvester equation, and compute polar decomposition, showing that Frobenius inversion can be more efficient than LU/Cholesky decomposition with negligible loss in accuracy. A side result is a generalization of Gauss multiplication to iterated quadratic extensions, which we show is intimately related to the Karatsuba algorithm for fast integer multiplication and multidimensional fast Fourier transform., Comment: 29 pages, 8 figures

The non-negativity of a function on a finite abelian group can be certified by its Fourier sum of squares (FSOS). In this paper, we propose a method of certifying the non-negativity of an integer-valued function by an FSOS certificate, which is defined to be an FSOS with a small error. We prove the existence of exponentially sparse polynomial and rational FSOS certificates and we provide two methods to validate them. As a consequence of the aforementioned existence theorems, we propose a semidefinite programming (SDP)-based algorithm to efficiently compute a sparse FSOS certificate. For applications, we consider certificate problems for maximum satisfiability (MAX-SAT) and maximum k-colorable subgraph (MkCS) and demonstrate our theoretical results and algorithm by numerical experiments.

Based on the observation that $\mathbb{Q}^{(p-1) \times (p-1)}$ is isomorphic to a quotient skew polynomial ring, we propose a new method for $(p-1)\times (p-1)$ matrix multiplication over $\mathbb{Q}$, where $p$ is a prime number. The main feature of our method is the acceleration for matrix multiplication if the product is skew-sparse. Based on the new method, we design a deterministic algorithm with complexity $O(T^{\omega-2} p^2)$, where $T\le p-1$ is a parameter determined by the skew-sparsity of input matrices and $\omega$ is the asymptotic exponent of matrix multiplication. Moreover, by introducing randomness, we also propose a probabilistic algorithm with complexity $O^\thicksim(t^{\omega-2}p^2+p^2\log\frac{1}{\nu})$, where $t\le p-1$ is the skew-sparsity of the product and $\nu$ is the probability parameter.

Due to the multi-linearity of tensors, most algorithms for tensor optimization problems are designed based on the block coordinate descent method. Such algorithms are widely employed by practitioners for their implementability and effectiveness. However, these algorithms usually suffer from the lack of theoretical guarantee of global convergence and analysis of convergence rate. In this paper, we propose a block coordinate descent type algorithm for the low rank partially orthogonal tensor approximation problem and analyse its convergence behaviour. To achieve this, we carefully investigate the variety of low rank partially orthogonal tensors and its geometric properties related to the parameter space, which enable us to locate KKT points of the concerned optimization problem. With the aid of these geometric properties, we prove without any assumption that: (1) Our algorithm converges globally to a KKT point; (2) For any given tensor, the algorithm exhibits an overall sublinear convergence with an explicit rate which is sharper than the usual $O(1/k)$ for first order methods in nonconvex optimization; {(3)} For a generic tensor, our algorithm converges $R$-linearly., Comment: 60 pages

The problem of verifying the nonnegativity of a function on a finite abelian group is a long-standing challenging problem. The basic theory of representation theory of finite groups indicates that a function $f$ on a finite abelian group $G$ can be written as a linear combination of characters of irreducible representations of $G$ by $ f(x)=\sum_{\chi \in \widehat{G}} \widehat{f} (\chi)\chi(x)$, where $\widehat{G}$ is the dual group of $G$ consisting of all characters of $G$ and $ \widehat{f} (\chi)$ is the Fourier coefficient of $f$ at $\chi \in \widehat{G}$. In this paper, we show that by performing the fast (inverse) Fourier transform, we are able to compute a sparse Fourier sum of squares (FSOS) certificate of $f$ on a finite abelian group $G$ with complexity \if $\operatorname{O}\left(|G| \log(|G|)+\log(k_{\min})\operatorname{SDP}(2k_{\min})\right)$,\fi that is quasi-linear in the order of $G$ and polynomial in the FSOS sparsity \if $k_{\min}$\fi of $f$. Moreover, for a nonnegatvie function $f$ on a finite abelian group $G$ and a set $S \subset \widehat{G}$, we give a lower bound of the constant $M$ such that $f+M$ admits an FSOS supported on} $S$. We demonstrate the efficiency of the proposed algorithm by numerical experiments on various abelian groups of orders up to $10^7$. As applications, we also solve some combinatorial optimization problems and the sum of Hermitian squares (SOHS) problem \if on $\mathbb{T}^n$\fi by sparse FSOS.

There are two widely used models for the Grassmannian $\operatorname{Gr}(k,n)$, as the set of equivalence classes of orthogonal matrices $\operatorname{O}(n)/(\operatorname{O}(k) \times \operatorname{O}(n-k))$, and as the set of trace-$k$ projection matrices $\{P \in \mathbb{R}^{n \times n} : P^{\mathsf{T}} = P = P^2,\; \operatorname{tr}(P) = k\}$. The former, standard in manifold optimization, has the advantage of giving numerically stable algorithms but the disadvantage of having to work with equivalence classes of matrices. The latter, widely used in coding theory and probability, has the advantage of using actual matrices (as opposed to equivalence classes) but working with projection matrices is numerically unstable. We present an alternative that has both advantages and suffers from neither of the disadvantages; by representing $k$-dimensional subspaces as symmetric orthogonal matrices of trace $2k-n$, we obtain \[ \operatorname{Gr}(k,n) \cong \{Q \in \operatorname{O}(n) : Q^{\mathsf{T}} = Q, \; \operatorname{tr}(Q) = 2k -n\}. \] As with the other two models, we show that differential geometric objects and operations -- tangent vector, metric, normal vector, exponential map, geodesic, parallel transport, gradient, Hessian, etc -- have closed-form analytic expressions that are computable with standard numerical linear algebra. In the proposed model, these expressions are considerably simpler, a result of representing $\operatorname{Gr}(k,n)$ as a linear section of a compact matrix Lie group $\operatorname{O}(n)$, and can be computed with at most one QR decomposition and one exponential of a special skew-symmetric matrix that takes only $O(nk(n-k))$ time. In particular, we completely avoid eigen- and singular value decompositions in our steepest descent, conjugate gradient, quasi-Newton, and Newton methods for the Grassmannian., Comment: 34 pages, 4 figures

Amidst the growing interest in nonparametric regression, we address a significant challenge in Gaussian processes(GP) applied to manifold-based predictors. Existing methods primarily focus on low dimensional constrained domains for heat kernel estimation, limiting their effectiveness in higher-dimensional manifolds. Our research proposes an intrinsic approach for constructing GP on general manifolds such as orthogonal groups, unitary groups, Stiefel manifolds and Grassmannian manifolds. Our methodology estimates the heat kernel by simulating Brownian motion sample paths using the exponential map, ensuring independence from the manifold's embedding. The introduction of our strip algorithm, tailored for manifolds with extra symmetries, and the ball algorithm, designed for arbitrary manifolds, constitutes our significant contribution. Both algorithms are rigorously substantiated through theoretical proofs and numerical testing, with the strip algorithm showcasing remarkable efficiency gains over traditional methods. This intrinsic approach delivers several key advantages, including applicability to high dimensional manifolds, eliminating the requirement for global parametrization or embedding. We demonstrate its practicality through regression case studies (torus knots and eight dimensional projective spaces) and by developing binary classifiers for real world datasets (gorilla skulls planar images and diffusion tensor images). These classifiers outperform traditional methods, particularly in limited data scenarios.

This paper discusses the problem of symmetric tensor decomposition on a given variety $X$: decomposing a symmetric tensor into the sum of tensor powers of vectors contained in $X$. In this paper, we first study geometric and algebraic properties of such decomposable tensors, which are crucial to the practical computations of such decompositions. For a given tensor, we also develop a criterion for the existence of a symmetric decomposition on $X$. Secondly and most importantly, we propose a method for computing symmetric tensor decompositions on an arbitrary $X$. As a specific application, Vandermonde decompositions for nonsymmetric tensors can be computed by the proposed algorithm.

Low rank orthogonal tensor approximation (LROTA) is an important problem in tensor computations and their applications. A classical and widely used algorithm is the alternating polar decomposition method (APD). In this article, an improved version iAPD of the classical APD is proposed. For the first time, all the following four fundamental properties are established for iAPD: (i) the algorithm converges globally and the whole sequence converges to a KKT point without any assumption; (ii) it exhibits an overall sublinear convergence with an explicit rate which is sharper than the usual $O(1/k)$ for first order methods in optimization; (iii) more importantly, it converges $R$-linearly for a generic tensor without any assumption; (iv) for almost all LROTA problems, iAPD reduces to APD after finitely many iterations if it converges to a local minimizer., Comment: 39 pages

A flag is a sequence of nested subspaces. Flags are ubiquitous in numerical analysis, arising in finite elements, multigrid, spectral, and pseudospectral methods for numerical PDE; they arise in the form of Krylov subspaces in matrix computations, and as multiresolution analysis in wavelets constructions. They are common in statistics too --- principal component, canonical correlation, and correspondence analyses may all be viewed as methods for extracting flags from a data set. The main goal of this article is to develop the tools needed for optimizing over a set of flags, which is a smooth manifold called the flag manifold, and it contains the Grassmannian as the simplest special case. We will derive closed-form analytic expressions for various differential geometric objects required for Riemannian optimization algorithms on the flag manifold; introducing various systems of extrinsic coordinates that allow us to parameterize points, metrics, tangent spaces, geodesics, distance, parallel transport, gradients, Hessians in terms of matrices and matrix operations; and thereby permitting us to formulate steepest descent, conjugate gradient, and Newton algorithms on the flag manifold using only standard numerical linear algebra., Comment: 27 pages, 2 figures

We introduce in this paper a manifold optimization framework that utilizes semi-Riemannian structures on the underlying smooth manifolds. Unlike in Riemannian geometry, where each tangent space is equipped with a positive definite inner product, a semi-Riemannian manifold allows the metric tensor to be indefinite on each tangent space, i.e., possessing both positive and negative definite subspaces; differential geometric objects such as geodesics and parallel-transport can be defined on non-degenerate semi-Riemannian manifolds as well, and can be carefully leveraged to adapt Riemannian optimization algorithms to the semi-Riemannian setting. In particular, we discuss the metric independence of manifold optimization algorithms, and illustrate that the weaker but more general semi-Riemannian geometry often suffices for the purpose of optimizing smooth functions on smooth manifolds in practice., Comment: 36 pages, 3 figures, 9 pages of supplemental materials

We construct a new class of three-dimensional topological quantum field theories (3d TQFTs) by considering generalized Argyres-Douglas theories on $S^1 \times M_3$ with a non-trivial holonomy of a discrete global symmetry along the $S^1$. For the minimal choice of the holonomy, the resulting 3d TQFTs are non-unitary and semisimple, thus distinguishing themselves from theories of Chern-Simons and Rozansky-Witten types respectively. Changing the holonomy performs a Galois transformation on the TQFT, which can sometimes give rise to more familiar unitary theories such as the $(G_2)_1$ and $(F_4)_1$ Chern-Simons theories. Our construction is based on an intriguing relation between topologically twisted partition functions, wild Hitchin characters, and chiral algebras which, when combined together, relate Coulomb branch and Higgs branch data of the same 4d $\mathcal{N}=2$ theory. We test our proposal by applying localization techniques to the conjectural $\mathcal{N}=1$ UV Lagrangian descriptions of the $(A_1,A_2)$, $(A_1,A_3)$ and $(A_1,D_3)$ theories., Comment: 6 pages

The Grassmannian of affine subspaces is a natural generalization of both the Euclidean space, points being zero-dimensional affine subspaces, and the usual Grassmannian, linear subspaces being special cases of affine subspaces. We show that, like the Grassmannian, the affine Grassmannian has rich geometrical and topological properties: It has the structure of a homogeneous space, a differential manifold, an algebraic variety, a vector bundle, a classifying space, among many more structures; furthermore; it affords an analogue of Schubert calculus and its (co)homology and homotopy groups may be readily determined. On the other hand, like the Euclidean space, the affine Grassmannian serves as a concrete computational platform on which various distances, metrics, probability densities may be explicitly defined and computed via numerical linear algebra. Moreover, many standard problems in machine learning and statistics --- linear regression, errors-in-variables regression, principal components analysis, support vector machines, or more generally any problem that seeks linear relations among variables that either best represent them or separate them into components --- may be naturally formulated as problems on the affine Grassmannian., Comment: 25 pages, 1 figure. This article contains material in earlier versions of arXiv:1607.01833, which has been split into two parts at an editor's recommendation

We show how the Riemannian distance on $\mathbb{S}^n_{++}$, the cone of $n\times n$ real symmetric or complex Hermitian positive definite matrices, may be used to naturally define a distance between two such matrices of different dimensions. Given that $\mathbb{S}^n_{++}$ also parameterizes $n$-dimensional ellipsoids, and inner products on $\mathbb{R}^n$, $n \times n$ covariance matrices of nondegenerate probability distributions, this gives us a natural way to define a geometric distance between a pair of such objects of different dimensions., Comment: 9 pages

We study path-connectedness and homotopy groups of sets of tensors defined by tensor rank, border rank, multilinear rank, as well as their symmetric counterparts for symmetric tensors. We show that over $\mathbb{C}$, the set of rank-$r$ tensors and the set of symmetric rank-$r$ symmetric tensors are both path-connected if $r$ is not more than the complex generic rank; these results also extend to border rank and symmetric border rank over $\mathbb{C}$. Over $\mathbb{R}$, the set of rank-$r$ tensors is path-connected if it has the expected dimension but the corresponding result for symmetric rank-$r$ symmetric $d$-tensors depends on the order $d$: connected when $d$ is odd but not when $d$ is even. Border rank and symmetric border rank over $\mathbb{R}$ have essentially the same path-connectedness properties as rank and symmetric rank over $\mathbb{R}$. When $r$ is greater than the complex generic rank, we are unable to discern any general pattern: For example, we show that border-rank-three tensors in $\mathbb{R}^2 \otimes \mathbb{R}^2 \otimes \mathbb{R}^2$ fall into four connected components. For multilinear rank, the manifold of $d$-tensors of multilinear rank $(r_1,\dots,r_d)$ in $\mathbb{C}^{n_1} \otimes \cdots \otimes \mathbb{C}^{n_d}$ is always path-connected, and the same is true in $\mathbb{R}^{n_1} \otimes \cdots \otimes \mathbb{R}^{n_d}$ unless $n_i = r_i = \prod_{j \ne i} r_j$ for some $i\in\{1, \dots, d\}$. Beyond path-connectedness, we determine, over both $\mathbb{R}$ and $\mathbb{C}$, the fundamental and higher homotopy groups of the set of tensors of a fixed small rank, and, taking advantage of Bott periodicity, those of the manifold of tensors of a fixed multilinear rank. We also obtain analogues of these results for symmetric tensors of a fixed symmetric rank or a fixed symmetric multilinear rank., Comment: 31 pages

In problems involving approximation, completion, denoising, dimension reduction, estimation, interpolation, modeling, order reduction, regression, etc, we argue that the near-universal practice of assuming that a function, matrix, or tensor (which we will see are all the same object in this context) has \emph{low rank} may be ill-justified. There are many natural instances where the object in question has high rank with respect to the classical notions of rank: matrix rank, tensor rank, multilinear rank --- the latter two being the most straightforward generalizations of the former. To remedy this, we show that one may vastly expand these classical notions of ranks: Given any undirected graph $G$, there is a notion of $G$-rank associated with $G$, which provides us with as many different kinds of ranks as there are undirected graphs. In particular, the popular tensor network states in physics (e.g., \textsc{mps}, \textsc{ttns}, \textsc{peps}) may be regarded as functions of a specific $G$-rank for various choices of $G$. Among other things, we will see that a function, matrix, or tensor may have very high matrix, tensor, or multilinear rank and yet very low $G$-rank for some $G$. In fact the difference is in the orders of magnitudes and the gaps between $G$-ranks and these classical ranks are arbitrarily large for some important objects in computer science, mathematics, and physics. Furthermore, we show that there is a $G$ such that almost every tensor has $G$-rank exponentially lower than its rank or the dimension of its ambient space., Comment: 37 pages, 7 figures

We study S-duality of Argyres-Douglas theories obtained by compactification of 6d (2,0) theories of ADE type on a sphere with irregular punctures. The weakly coupled descriptions are given by the degeneration limit of auxiliary Riemann sphere with marked points, among which three punctured sphere represents isolated superconformal theories. We also discuss twisted irregular punctures and their S-duality., Comment: 56 pages, 13 figures

Hankel tensors are generalizations of Hankel matrices. This article studies the relations among various ranks of Hankel tensors. We give an algorithm that can compute the Vandermonde ranks and decompositions for all Hankel tensors. For a generic $n$-dimensional Hankel tensor of even order or order three, we prove that the the cp rank, symmetric rank, border rank, symmetric border rank, and Vandermonde rank all coincide with each other. In particular, this implies that the Comon's conjecture is true for generic Hankel tensors when the order is even or three. Some open questions are also posed.

We analyze classical and quantum chiral ring relations of four dimensional ${\cal N} = 1$ adjoint SQCD with superpotential turned on for the adjoint field. In particular, for the mass deformed theory we obtain the complete on shell vacuum expectation value for various gauge invariant chiral operators and find non-trivial gaugino condensations. When approaching to massless limit nontrivial flat directions in the moduli space of vacua appear, where the Coulomb branch can be naturally classified and the Higgs branch receives quantum corrections. We argue that the solution of the chiral ring is in one-to-one correspondence with supersymmetric vacua, provided that an additional Konishi anomaly equation is included., Comment: 42 pages, 2 figures

We use Coulomb branch indices of Argyres-Douglas theories on $S^1 \times L(k,1)$ to quantize moduli spaces ${\cal M}_H$ of wild/irregular Hitchin systems. In particular, we obtain formulae for the "wild Hitchin characters" -- the graded dimensions of the Hilbert spaces from quantization -- for four infinite families of ${\cal M}_H$, giving access to many interesting geometric and topological data of these moduli spaces. We observe that the wild Hitchin characters can always be written as a sum over fixed points in ${\cal M}_H$ under the $U(1)$ Hitchin action, and a limit of them can be identified with matrix elements of the modular transform $ST^kS$ in certain two-dimensional chiral algebras. Although naturally fitting into the geometric Langlands program, the appearance of chiral algebras, which was known previously to be associated with Schur operators but not Coulomb branch operators, is somewhat surprising., Comment: 47+20 pages, 3 figures. v2: reference added, misprints corrected. v3: added corrections according to journal referee

The affine Grassmannian is a noncompact smooth manifold that parameterizes all affine subspaces of a fixed dimension. It is a natural generalization of Euclidean space, points being zero-dimensional affine subspaces. We will realize the affine Grassmannian as a matrix manifold and extend Riemannian optimization algorithms including steepest descent, Newton method, and conjugate gradient, to real-valued functions on the affine Grassmannian. Like their counterparts for the Grassmannian, these algorithms are in the style of Edelman--Arias--Smith --- they rely only on standard numerical linear algebra and are readily computable., Comment: 18 pages, 3 figures

In this paper, we show the equivalence between two seemingly distinct 2d TQFTs: one comes from the "Coulomb branch index" of the class S theory $T[\Sigma,G]$ on $L(k,1) \times S^1$, the other is the $^LG$ "equivariant Verlinde formula", or equivalently partition function of $^LG_{\mathbb{C}}$ complex Chern-Simons theory on $\Sigma\times S^1$. We first derive this equivalence using the M-theory geometry and show that the gauge groups appearing on the two sides are naturally $G$ and its Langlands dual $^LG$. When $G$ is not simply-connected, we provide a recipe of computing the index of $T[\Sigma,G]$ as summation over indices of $T[\Sigma,\tilde{G}]$ with non-trivial background 't Hooft fluxes, where $\tilde{G}$ is the simply-connected group with the same Lie algebra. Then we check explicitly this relation between the Coulomb index and the equivariant Verlinde formula for $G=SU(2)$ or $SO(3)$. In the end, as an application of this newly found relation, we consider the more general case where $G$ is $SU(N)$ or $PSU(N)$ and show that equivariant Verlinde algebra can be derived using field theory via (generalized) Argyres-Seiberg duality. We also attach a Mathematica notebook that can be used to compute the $SU(3)$ equivariant Verlinde coefficients., Comment: 40 pages, 7 figures, Mathematica Notebook attached; v2: misprints corrected; v3: Acknowledgement added, corrections made based on the journal version

The idea of decomposing a matrix into a product of structured matrices such as triangular, orthogonal, diagonal matrices is a milestone of numerical computations. In this paper, we describe six new classes of matrix decompositions, extending our work in arXiv:1307.5132. We prove that every $n\times n$ matrix is a product of finitely many bidiagonal, skew symmetric (when n is even), generic, companion matrices and generalized Vandermonde matrices, respectively. We also prove that a generic $n\times n$ centrosymmetric matrix is a product of finitely many symmetric Toeplitz (resp. persymmetric Hankel) matrices. We determine an upper bound of the number of structured matrices needed to decompose a matrix for each case.

The goal of cryo-electron microscopy (EM) is to reconstruct the 3-dimensional structure of a molecule from a collection of its 2-dimensional projected images. In this article, we show that the basic premise of cryo-EM --- patching together 2-dimensional projections to reconstruct a 3-dimensional object --- is naturally one of Cech cohomology with SO(2)-coefficients. We deduce that every cryo-EM reconstruction problem corresponds to an oriented circle bundle on a simplicial complex, allowing us to classify cryo-EM problems via principal bundles. In practice, the 2-dimensional images are noisy and a main task in cryo-EM is to denoise them. We will see how the aforementioned insights can be used towards this end., Comment: 27 pages, 5 figures

We present explicit algorithms for computing structured matrix-vector products that are optimal in the sense of Strassen, i.e., using a provably minimum number of multiplications. These structures include Toeplitz/Hankel/circulant, symmetric, Toeplitz-plus-Hankel, sparse, and multilevel structures. The last category include \textsc{bttb}, \textsc{bhhb}, \textsc{bccb} but also any arbitrarily complicated nested structures built out of other structures., Comment: 5 pages

We discuss a generalization of the Cohn-Umans method, a potent technique developed for studying the bilinear complexity of matrix multiplication by embedding matrices into an appropriate group algebra. We investigate how the Cohn-Umans method may be used for bilinear operations other than matrix multiplication, with algebras other than group algebras, and we relate it to Strassen's tensor rank approach, the traditional framework for investigating bilinear complexity. To demonstrate the utility of the generalized method, we apply it to find the fastest algorithms for forming structured matrix-vector product, the basic operation underlying iterative algorithms for structured matrices. The structures we study include Toeplitz, Hankel, circulant, symmetric, skew-symmetric, f-circulant, block-Toeplitz-Toeplitz-block, triangular Toeplitz matrices, Toeplitz-plus-Hankel, sparse/banded/triangular. Except for the case of skew-symmetric matrices, for which we have only upper bounds, the algorithms derived using the generalized Cohn-Umans method in all other instances are the fastest possible in the sense of having minimum bilinear complexity. We also apply this framework to a few other bilinear operations including matrix-matrix, commutator, simultaneous matrix products, and briefly discuss the relation between tensor nuclear norm and numerical stability., Comment: 37 pages

A tensor $\mathcal T\in \mathbb T(\mathbb C^n,m+1)$, the space of tensors of order $m+1$ and dimension $n$ with complex entries, has $nm^{n-1}$ eigenvalues (counted with algebraic multiplicities). The inverse eigenvalue problem for tensors is a generalization of that for matrices. Namely, given a multiset $S\in \mathbb C^{nm^{n-1}}/\mathfrak{S}(nm^{n-1})$ of total multiplicity $nm^{n-1}$, is there a tensor in $\mathbb T(\mathbb C^n,m+1)$ such that the multiset of eigenvalues of $\mathcal{T}$ is exact $S$? The solvability of the inverse eigenvalue problem for tensors is studied in this paper. With tools from algebraic geometry, it is proved that the necessary and sufficient condition for this inverse problem to be generically solvable is $m=1,\ \text{or }n=2,\ \text{or }(n,m)=(3,2),\ (4,2),\ (3,3)$., Comment: 20 pages

We test the 3d-3d correspondence for theories that are labelled by Lens spaces. We find a full agreement between the index of the 3d ${\cal N}=2$ "Lens space theory" $T[L(p,1)]$ and the partition function of complex Chern-Simons theory on $L(p,1)$. In particular, for $p=1$, we show how the familiar $S^3$ partition function of Chern-Simons theory arises from the index of a free theory. For large $p$, we find that the index of $T[L(p,1)]$ becomes a constant independent of $p$. In addition, we study $T[L(p,1)]$ on the squashed three-sphere $S^3_b$. This enables us to see clearly, at the level of partition function, to what extent $G_\mathbb{C}$ complex Chern-Simons theory can be thought of as two copies of Chern-Simons theory with compact gauge group $G$., Comment: 27 pages. v2: misprints corrected, references added. v3: misprints corrected, a clarification added

We study in this article multiplicities of eigenvalues of tensors. There are two natural multiplicities associated to an eigenvalue $\lambda$ of a tensor: algebraic multiplicity $\operatorname{am}(\lambda)$ and geometric multiplicity $\operatorname{gm}(\lambda)$. The former is the multiplicity of the eigenvalue as a root of the characteristic polynomial, and the latter is the dimension of the eigenvariety (i.e., the set of eigenvectors) corresponding to the eigenvalue. We show that the algebraic multiplicity could change along the orbit of tensors by the orthogonal linear group action, while the geometric multiplicity of the zero eigenvalue is invariant under this action, which is the main difficulty to study their relationships. However, we show that for a generic tensor, every eigenvalue has a unique (up to scaling) eigenvector, and both the algebraic multiplicity and geometric multiplicity are one. In general, we suggest for an $m$-th order $n$-dimensional tensor the relationship \[ \operatorname{am}(\lambda)\geq \operatorname{gm}(\lambda)(m-1)^{\operatorname{gm}(\lambda)-1}. \] We show that it is true for serveral cases, especially when the eigenvariety contains a linear subspace of dimension $\operatorname{gm}(\lambda)$ in coordinate form. As both multiplicities are invariants under the orthogonal linear group action in the matrix counterpart, this generalizes the classical result for a matrix: the algebraic mutliplicity is not smaller than the geometric multiplicity.

We resolve a basic problem on subspace distances that often arises in applications: How can the usual Grassmann distance between equidimensional subspaces be extended to subspaces of different dimensions? We show that a natural solution is given by the distance of a point to a Schubert variety within the Grassmannian. This distance reduces to the Grassmann distance when the subspaces are equidimensional and does not depend on any embedding into a larger ambient space. Furthermore, it has a concrete expression involving principal angles, and is efficiently computable in numerically stable ways. Our results are largely independent of the Grassmann distance --- if desired, it may be substituted by any other common distances between subspaces. Our approach depends on a concrete algebraic geometric view of the Grassmannian that parallels the differential geometric perspective that is well-established in applied and computational mathematics., Comment: 20 pages, 1 figure

We show that every n-by-n matrix is generically a product of [n/2] + 1 Toeplitz matrices and always a product of at most 2n+5 Toeplitz matrices. The same result holds true if the word "Toeplitz" is replaced by "Hankel", and the generic bound [n/2] + 1 is sharp. We will see that these decompositions into Toeplitz or Hankel factors are unusual: We may not in general replace the subspace of Toeplitz or Hankel matrices by an arbitrary (2n-1)-dimensional subspace of n-by-n matrices. Furthermore such decompositions do not exist if we require the factors to be symmetric Toeplitz, persymmetric Hankel, or circulant matrices, even if we allow an infinite number of factors. Lastly, we discuss how the Toeplitz and Hankel decompositions of a generic matrix may be computed by either (i) solving a system of linear and quadratic equations if the number of factors is required to be [n/2] + 1, or (ii) Gaussian elimination in O(n^3) time if the number of factors is allowed to be 2n., Comment: 18 pages