Search

A ReLU neural network leads to a finite polyhedral decomposition of input space and a corresponding finite dual graph. We show that while this dual graph is a coarse quantization of input space, it is sufficiently robust that it can be combined with persistent homology to detect homological signals of manifolds in the input space from samples. This property holds for a variety of networks trained for a wide range of purposes that have nothing to do with this topological application. We found this feature to be surprising and interesting; we hope it will also be useful., Comment: Accepted by Proceedings of the 2 nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML) at the 40 th In- ternational Conference on Machine Learning

A common tool in the theory of numerical semigroups is to interpret a desired class of semigroups as the integer lattice points in a rational polyhedron in order to leverage computational and enumerative techniques from polyhedral geometry. Most arguments of this type make use of a parametrization of numerical semigroups with fixed multiplicity $m$ in terms of their $m$-Ap\'{e}ry sets, giving a representation called Kunz coordinates which obey a collection of inequalities defining the Kunz polyhedron. In this work, we introduce a new class of polyhedra describing numerical semigroups in terms of a truncated addition table of their sporadic elements. Applying a classical theorem of Ehrhart to slices of these polyhedra, we prove that the number of numerical semigroups with $n$ sporadic elements and Frobenius number $f$ is polynomial up to periodicity, or quasi-polynomial, as a function of $f$ for fixed $n$. We also generalize this approach to higher dimensions to demonstrate quasi-polynomial growth of the number of affine semigroups with a fixed number of elements, and all gaps, contained in an integer dilation of a fixed polytope., Comment: 15 pages

Finding prototypes (e.g., mean and median) for a dataset is central to a number of common machine learning algorithms. Subspaces have been shown to provide useful, robust representations for datasets of images, videos and more. Since subspaces correspond to points on a Grassmann manifold, one is led to consider the idea of a subspace prototype for a Grassmann-valued dataset. While a number of different subspace prototypes have been described, the calculation of some of these prototypes has proven to be computationally expensive while other prototypes are affected by outliers and produce highly imperfect clustering on noisy data. This work proposes a new subspace prototype, the flag median, and introduces the FlagIRLS algorithm for its calculation. We provide evidence that the flag median is robust to outliers and can be used effectively in algorithms like Linde-Buzo-Grey (LBG) to produce improved clusterings on Grassmannians. Numerical experiments include a synthetic dataset, the MNIST handwritten digits dataset, the Mind's Eye video dataset and the UCF YouTube action dataset. The flag median is compared the other leading algorithms for computing prototypes on the Grassmannian, namely, the $\ell_2$-median and to the flag mean. We find that using FlagIRLS to compute the flag median converges in $4$ iterations on a synthetic dataset. We also see that Grassmannian LBG with a codebook size of $20$ and using the flag median produces at least a $10\%$ improvement in cluster purity over Grassmannian LBG using the flag mean or $\ell_2$-median on the Mind's Eye dataset.

Deep Learning Recommendation Models (DLRM) are widespread, account for a considerable data center footprint, and grow by more than 1.5x per year. With model size soon to be in terabytes range, leveraging Storage ClassMemory (SCM) for inference enables lower power consumption and cost. This paper evaluates the major challenges in extending the memory hierarchy to SCM for DLRM, and presents different techniques to improve performance through a Software Defined Memory. We show how underlying technologies such as Nand Flash and 3DXP differentiate, and relate to real world scenarios, enabling from 5% to 29% power savings., Comment: 14 pages, 5 figures

A ReLU neural network determines/is a continuous piecewise linear map from an input space to an output space. The weights in the neural network determine a decomposition of the input space into convex polytopes and on each of these polytopes the network can be described by a single affine mapping. The structure of the decomposition, together with the affine map attached to each polytope, can be analyzed to investigate the behavior of the associated neural network., Comment: 18 pages, 12 figures, 2 tables, submitted to SIMODS

The shape and orientation of data clouds reflect variability in observations that can confound pattern recognition systems. Subspace methods, utilizing Grassmann manifolds, have been a great aid in dealing with such variability. However, this usefulness begins to falter when the data cloud contains sufficiently many outliers corresponding to stray elements from another class or when the number of data points is larger than the number of features. We illustrate how nested subspace methods, utilizing flag manifolds, can help to deal with such additional confounding factors. Flag manifolds, which are parameter spaces for nested subspaces, are a natural geometric generalization of Grassmann manifolds. To make practical comparisons on a flag manifold, algorithms are proposed for determining the distances between points $[A], [B]$ on a flag manifold, where $A$ and $B$ are arbitrary orthogonal matrix representatives for $[A]$ and $[B]$, and for determining the initial direction of these minimal length geodesics. The approach is illustrated in the context of (hyper) spectral imagery showing the impact of ambient dimension, sample dimension, and flag structure., Comment: 15 pages, 8 figures

Lens spaces are a family of manifolds that have been a source of many interesting phenomena in topology and differential geometry. Their concrete construction, as quotients of odd-dimensional spheres by a free linear action of a finite cyclic group, allows a deeper analysis of their structure. In this paper, we consider the problem of moments for the distance function between randomly selected pairs of points on homogeneous three-dimensional lens spaces. We give a derivation of a recursion relation for the moments, a formula for the $k$th moment, and a formula for the moment generating function, as well as an explicit formula for the volume of balls of all radii in these lens spaces., Comment: 17 pages, 4 figures

Apolarity is an important tool in commutative algebra and algebraic geometry which studies a form, $f$, by the action of polynomial differential operators on $f$. The quotient of all polynomial differential operators by those which annihilate $f$ is called the apolar algebra of $f$. In general, the apolar algebra of a form is useful for determining its Waring rank, which can be seen as the problem of decomposing the supersymmetric tensor, associated to the form, minimally as a sum of rank one supersymmetric tensors. In this article we study the apolar algebra of a product of linear forms, which generalizes the case of monomials and connects to the geometry of hyperplane arrangements. In the first part of the article we provide a bound on the Waring rank of a product of linear forms under certain genericity assumptions; for this we use the defining equations of so-called star configurations due to Geramita, Harbourne, and Migliore. In the second part of the article we use the computer algebra system Bertini, which operates by homotopy continuation methods, to solve certain rank equations for catalecticant matrices. Our computations suggest that, up to a change of variables, there are exactly six homogeneous polynomials of degree six in three variables which factor completely as a product of linear forms defining an irreducible multi-arrangement and whose apolar algebras have dimension six in degree three. As a consequence of these calculations, we find six cases of such forms with cactus rank six, five of which also have Waring rank six. Among these are products defining subarrangements of the braid and Hessian arrangements., Comment: 14 pages, 2 tables

Flag manifolds are generalizations of projective spaces and other Grassmannians: they parametrize flags, which are nested sequences of subspaces in a given vector space. These are important objects in algebraic and differential geometry, but are also increasingly being used in data science, where many types of data are properly understood as subspaces rather than vectors. In this paper we discuss partially oriented flag manifolds, which parametrize flags in which some of the subspaces may be endowed with an orientation. We compute the expected distance between random points on some low-dimensional examples, which we view as a statistical baseline against which to compare the distances between particular partially oriented flags coming from geometry or data., Comment: 13 pages, 3 figures

Let $G$ be a group acting properly and by isometries on a metric space $X$; it follows that the quotient or orbit space $X/G$ is also a metric space. We study the Vietoris-Rips and \v{C}ech complexes of $X/G$. Whereas (co)homology theories for metric spaces let the scale parameter of a Vietoris-Rips or \v{C}ech complex go to zero, and whereas geometric group theory requires the scale parameter to be sufficiently large, we instead consider intermediate scale parameters (neither tending to zero nor to infinity). As a particular case, we study the Vietoris-Rips and \v{C}ech thickenings of projective spaces at the first scale parameter where the homotopy type changes.

A numerical semigroup is a submonoid of $\mathbb N$ with finite complement in $\mathbb N$. A generalized numerical semigroup is a submonoid of $\mathbb{N}^{d}$ with finite complement in $\mathbb{N}^{d}$. In the context of numerical semigroups, Wilf's conjecture is a long standing open problem whose study has led to new mathematics and new ways of thinking about monoids. A natural extension of Wilf's conjecture, to the class of $\mathcal C$-semigroups, was proposed by Garc\'ia-Garc\'ia, Mar\'in-Arag\'on, and Vigneron-Tenorio. In this paper, we propose a different generalization of Wilf's conjecture, to the setting of generalized numerical semigroups, and prove the conjecture for several large families including the irreducible, symmetric, and monomial case. We also discuss the relationship of our conjecture to the extension proposed by Garc\'ia-Garc\'ia, Mar\'in-Arag\'on, and Vigneron-Tenorio., Comment: 22 pages, 3 figures

Let $\mathbb{N}^{d}$ be the $d$-dimensional monoid of non-negative integers. A generalized numerical semigroup is a submonoid $ S\subseteq \mathbb{N}^d$ such that $H(S)=\mathbb{N}^d \setminus S$ is a finite set. We introduce irreducible generalized numerical semigroups and characterize them in terms of the cardinality of a special subset of $H(S)$. In particular, we describe relaxed monomial orders on $\mathbb N^d$, define the Frobenius element of $S$ with respect to a given relaxed monomial order, and show that the Frobenius element of $S$ is independent of the order if the generalized numerical semigroup is irreducible., Comment: 15 pages

Compressive sensing (CS) is a method of sampling which permits some classes of signals to be reconstructed with high accuracy even when they were under-sampled. In this paper we explore a phenomenon in which bandwise CS sampling of a hyperspectral data cube followed by reconstruction can actually result in amplification of chemical signals contained in the cube. Perhaps most surprisingly, chemical signal amplification generally seems to increase as the level of sampling decreases. In some examples, the chemical signal is significantly stronger in a data cube reconstructed from 10% CS sampling than it is in the raw, 100% sampled data cube. We explore this phenomenon in two real-world datasets including the Physical Sciences Inc. Fabry-P\'{e}rot interferometer sensor multispectral dataset and the Johns Hopkins Applied Physics Lab FTIR-based longwave infrared sensor hyperspectral dataset. Each of these datasets contains the release of a chemical simulant, such as glacial acetic acid, triethyl phospate, and sulfur hexafluoride, and in all cases we use the adaptive coherence estimator (ACE) to detect a target signal in the hyperspectral data cube. We end the paper by suggesting some theoretical justifications for why chemical signals would be amplified in CS sampled and reconstructed hyperspectral data cubes and discuss some practical implications., Comment: 10 pages

One of the fundamental assumptions of compressive sensing (CS) is that a signal can be reconstructed from a small number of samples by solving an optimization problem with the appropriate regularization term. Two standard regularization terms are the L1 norm and the total variation (TV) norm. We present a comparison of CS reconstruction results based on these two approaches in the context of chemical detection, and we demonstrate that optimization based on the L1 norm outperforms optimization based on the TV norm. Our comparison is driven by CS sampling, reconstruction, and chemical detection in two real-world datasets: the Physical Sciences Inc. Fabry-P\'{e}rot interferometer sensor multispectral dataset and the Johns Hopkins Applied Physics Lab FTIR-based longwave infrared sensor hyperspectral dataset. Both datasets contain the release of a chemical simulant such as glacial acetic acid, triethyl phosphate, and sulfur hexafluoride. For chemical detection we use the adaptive coherence estimator (ACE) and bulk coherence, and we propose algorithmic ACE thresholds to define the presence or absence of a chemical of interest in both un-compressed data cubes and reconstructed data cubes. The un-compressed data cubes provide an approximate ground truth. We demonstrate that optimization based on either the L1 norm or TV norm results in successful chemical detection at a compression rate of 90%, but we show that L1 optimization is preferable. We present quantitative comparisons of chemical detection on reconstructions from the two methods, with an emphasis on the number of pixels with an ACE value above the threshold., Comment: 13 pages

Sampling is a fundamental aspect of any implementation of compressive sensing. Typically, the choice of sampling method is guided by the reconstruction basis. However, this approach can be problematic with respect to certain hardware constraints and is not responsive to domain-specific context. We propose a method for defining an order for a sampling basis that is optimal with respect to capturing variance in data, thus allowing for meaningful sensing at any desired level of compression. We focus on the Walsh-Hadamard sampling basis for its relevance to hardware constraints, but our approach applies to any sampling basis of interest. We illustrate the effectiveness of our method on the Physical Sciences Inc. Fabry-P\'{e}rot interferometer sensor multispectral dataset, the Johns Hopkins Applied Physics Lab FTIR-based longwave infrared sensor hyperspectral dataset, and a Colorado State University Swiss Ranger depth image dataset. The spectral datasets consist of simulant experiments, including releases of chemicals such as GAA and SF6. We combine our sampling and reconstruction with the adaptive coherence estimator (ACE) and bulk coherence for chemical detection and we incorporate an algorithmic threshold for ACE values to determine the presence or absence of a chemical. We compare results across sampling methods in this context. We have successful chemical detection at a compression rate of 90%. For all three datasets, we compare our sampling approach to standard orderings of sampling basis such as random, sequency, and an analog of sequency that we term `frequency.' In one instance, the peak signal to noise ratio was improved by over 30% across a test set of depth images., Comment: 15 pages

Dimensionality-reduction methods are a fundamental tool in the analysis of large data sets. These algorithms work on the assumption that the "intrinsic dimension" of the data is generally much smaller than the ambient dimension in which it is collected. Alongside their usual purpose of mapping data into a smaller dimension with minimal information loss, dimensionality-reduction techniques implicitly or explicitly provide information about the dimension of the data set. In this paper, we propose a new statistic that we call the $\kappa$-profile for analysis of large data sets. The $\kappa$-profile arises from a dimensionality-reduction optimization problem: namely that of finding a projection into $k$-dimensions that optimally preserves the secants between points in the data set. From this optimal projection we extract $\kappa,$ the norm of the shortest projected secant from among the set of all normalized secants. This $\kappa$ can be computed for any $k$; thus the tuple of $\kappa$ values (indexed by dimension) becomes a $\kappa$-profile. Algorithms such as the Secant-Avoidance Projection algorithm and the Hierarchical Secant-Avoidance Projection algorithm, provide a computationally feasible means of estimating the $\kappa$-profile for large data sets, and thus a method of understanding and monitoring their behavior. As we demonstrate in this paper, the $\kappa$-profile serves as a useful statistic in several representative settings: weather data, soundscape data, and dynamical systems data., Comment: Accepted to the 2018 IEEE International Conference on BIG DATA, 9 pages

A fundamental question in many data analysis settings is the problem of discerning the "natural" dimension of a data set. That is, when a data set is drawn from a manifold (possibly with noise), a meaningful aspect of the data is the dimension of that manifold. Various approaches exist for estimating this dimension, such as the method of Secant-Avoidance Projection (SAP). Intuitively, the SAP algorithm seeks to determine a projection which best preserves the lengths of all secants between points in a data set; by applying the algorithm to find the best projections to vector spaces of various dimensions, one may infer the dimension of the manifold of origination. That is, one may learn the dimension at which it is possible to construct a diffeomorphic copy of the data in a lower-dimensional Euclidean space. Using Whitney's embedding theorem, we can relate this information to the natural dimension of the data. A drawback of the SAP algorithm is that a data set with $T$ points has $O(T^2)$ secants, making the computation and storage of all secants infeasible for very large data sets. In this paper, we propose a novel algorithm that generalizes the SAP algorithm with an emphasis on addressing this issue. That is, we propose a hierarchical secant-based dimensionality-reduction method, which can be employed for data sets where explicitly calculating all secants is not feasible., Comment: To appear in the Proceedings of the 2018 IEEE High Performance Extreme Computing Conference, Waltham, MA USA

We use persistent homology in order to define a family of fractal dimensions, denoted $\mathrm{dim}_{\mathrm{PH}}^i(\mu)$ for each homological dimension $i\ge 0$, assigned to a probability measure $\mu$ on a metric space. The case of $0$-dimensional homology ($i=0$) relates to work by Michael J Steele (1988) studying the total length of a minimal spanning tree on a random sampling of points. Indeed, if $\mu$ is supported on a compact subset of Euclidean space $\mathbb{R}^m$ for $m\ge2$, then Steele's work implies that $\mathrm{dim}_{\mathrm{PH}}^0(\mu)=m$ if the absolutely continuous part of $\mu$ has positive mass, and otherwise $\mathrm{dim}_{\mathrm{PH}}^0(\mu)

Dimensionality-reduction techniques are a fundamental tool for extracting useful information from high-dimensional data sets. Because secant sets encode manifold geometry, they are a useful tool for designing meaningful data-reduction algorithms. In one such approach, the goal is to construct a projection that maximally avoids secant directions and hence ensures that distinct data points are not mapped too close together in the reduced space. This type of algorithm is based on a mathematical framework inspired by the constructive proof of Whitney's embedding theorem from differential topology. Computing all (unit) secants for a set of points is by nature computationally expensive, thus opening the door for exploitation of GPU architecture for achieving fast versions of these algorithms. We present a polynomial-time data-reduction algorithm that produces a meaningful low-dimensional representation of a data set by iteratively constructing improved projections within the framework described above. Key to our algorithm design and implementation is the use of GPUs which, among other things, minimizes the computational time required for the calculation of all secant lines. One goal of this report is to share ideas with GPU experts and to discuss a class of mathematical algorithms that may be of interest to the broader GPU community., Comment: To appear in the 17th IEEE International Symposium on Parallel and Distributed Computing, Geneva, Switzerland 2018

Endmember extraction plays a prominent role in a variety of data analysis problems as endmembers often correspond to data representing the purest or best representative of some feature. Identifying endmembers then can be useful for further identification and classification tasks. In settings with high-dimensional data, such as hyperspectral imagery, it can be useful to consider endmembers that are subspaces as they are capable of capturing a wider range of variations of a signature. The endmember extraction problem in this setting thus translates to finding the vertices of the convex hull of a set of points on a Grassmannian. In the presence of noise, it can be less clear whether a point should be considered a vertex. In this paper, we propose an algorithm to extract endmembers on a Grassmannian, identify subspaces of interest that lie near the boundary of a convex hull, and demonstrate the use of the algorithm on a synthetic example and on the 220 spectral band AVIRIS Indian Pines hyperspectral image., Comment: To appear in Proceedings of the 2018 IEEE Data Science Workshop, Lausanne, Switzerland

Principal Component Analysis can be performed over small domains of an embedded Riemannian manifold in order to relate the covariance analysis of the underlying point set with the local extrinsic and intrinsic curvature. We show that the volume of domains on a submanifold of general codimension, determined by the intersection with higher-dimensional cylinders and balls in the ambient space, have asymptotic expansions in terms of the mean and scalar curvatures. Moreover, we propose a generalization of the classical third fundamental form to general submanifolds and prove that the eigenvalue decomposition of the covariance matrices of the domains have asymptotic expansions with scale that contain the curvature information encoded by the traces of this tensor. In the case of hypersurfaces, this covariance analysis recovers the principal curvatures and principal directions, which can be used as descriptors at scale to build up estimators of the second fundamental form, and thus the Riemann tensor, of general submanifolds.

Integral invariants obtained from Principal Component Analysis on a small kernel domain of a submanifold encode important geometric information classically defined in differential-geometric terms. We generalize to hypersurfaces in any dimension major results known for surfaces in space, which in turn yield a method to estimate the extrinsic and intrinsic curvature of an embedded Riemannian submanifold of general codimension. In particular, integral invariants are defined by the volume, barycenter, and the EVD of the covariance matrix of the domain. We obtain the asymptotic expansion of such invariants for a spherical volume component delimited by a hypersurface and for the hypersurface patch created by ball intersetions, showing that the eigenvalues and eigenvectors can be used as multi-scale estimators of the principal curvatures and principal directions. This approach may be interpreted as performing statistical analysis on the underlying point-set of a submanifold in order to obtain geometric descriptors at scale with potential applications to Manifold Learning and Geometry Processing of point clouds.

Let $R=\mathbb K[x,y,z]$ be a standard graded polynomial ring where $\mathbb K$ is an algebraically closed field of characteristic zero. Let $M = \oplus_j M_j$ be a finite length graded $R$-module. We say that $M$ has the Weak Lefschetz Property if there is a homogeneous element $L$ of degree one in $R$ such that the multiplication map $\times L : M_j \rightarrow M_{j+1}$ has maximal rank for every $j$. The main result of this paper is to show that if $\mathcal E$ is a locally free sheaf of rank 2 on $\mathbb P^2$ then the first cohomology module of $\mathcal E$, $H^1_*(\mathbb P^2, \mathcal E)$, has the Weak Lefschetz Property., Comment: Nine pages; comments welcome

Let $L_1,\dots,L_s$ be line bundles on a smooth variety $X\subset \mathbb{P}^r$ and let $D_1,\dots,D_s$ be divisors on $X$ such that $D_i$ represents $L_i$. We give a probabilistic algorithm for computing the degree of intersections of polar classes which are in turn used for computing the Euler characteristic of linear combinations of $L_1,\dots,L_s$. The input consists of generators for the homogeneous ideals $I_X, I_{D_i} \subset \mathbb{C}[x_0,\ldots,x_r]$ defining $X$ and $D_i$.

The convex hull of a set of points, $C$, serves to expose extremal properties of $C$ and can help identify elements in $C$ of high interest. For many problems, particularly in the presence of noise, the true vertex set (and facets) may be difficult to determine. One solution is to expand the list of high interest candidates to points lying near the boundary of the convex hull. We propose a quadratic program for the purpose of stratifying points in a data cloud based on proximity to the boundary of the convex hull. For each data point, a quadratic program is solved to determine an associated weight vector. We show that the weight vector encodes geometric information concerning the point's relationship to the boundary of the convex hull. The computation of the weight vectors can be carried out in parallel, and for a fixed number of points and fixed neighborhood size, the overall computational complexity of the algorithm grows linearly with dimension. As a consequence, meaningful computations can be completed on reasonably large, high dimensional data sets.