Detecting the dimension of a hidden manifold from a point sample has become an important problem in the current data-driven era. Indeed, estimating the shape dimension is often the first step in studying the processes or phenomena associated to the d
ata. Among the many dimension detection algorithms proposed in various fields, a few can provide theoretical guarantee on the correctness of the estimated dimension. However, the correctness usually requires certain regularity of the input: the input points are either uniformly randomly sampled in a statistical setting, or they form the so-called $(varepsilon,delta)$-sample which can be neither too dense nor too sparse. Here, we propose a purely topological technique to detect dimensions. Our algorithm is provably correct and works under a more relaxed sampling condition: we do not require uniformity, and we also allow Hausdorff noise. Our approach detects dimension by determining local homology. The computation of this topological structure is much less sensitive to the local distribution of points, which leads to the relaxation of the sampling conditions. Furthermore, by leveraging various developments in computational topology, we show that this local homology at a point $z$ can be computed emph{exactly} for manifolds using Vietoris-Rips complexes whose vertices are confined within a local neighborhood of $z$. We implement our algorithm and demonstrate the accuracy and robustness of our method using both synthetic and real data sets.
We study the effect of edge contractions on simplicial homology because these contractions have turned to be useful in various applications involving topology. It was observed previously that contracting edges that satisfy the so called link conditio
n preserves homeomorphism in low dimensional complexes, and homotopy in general. But, checking the link condition involves computation in all dimensions, and hence can be costly, especially in high dimensional complexes. We define a weaker and more local condition called the p-link condition for each dimension p, and study its effect on edge contractions. We prove the following: (i) For homology groups, edges satisfying the p- and (p-1)-link conditions can be contracted without disturbing the p-dimensional homology group. (ii) For relative homology groups, the (p-1)-, and the (p-2)-link conditions suffice to guarantee that the contraction does not introduce any new class in any of the resulting relative homology groups, though some of the existing classes can be destroyed. Unfortunately, the surjection in relative homolgy groups does not guarantee that no new relative torsion is created. (iii) For torsions, edges satisfying the p-link condition alone can be contracted without creating any new relative torsion and the p-link condition cannot be avoided. The results on relative homology and relative torsion are motivated by recent results on computing optimal homologous chains, which state that such problems can be solved by linear programming if the complex has no relative torsion. Edge contractions that do not introduce new relative torsions, can safely be availed in these contexts.
The efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips an
d witness complexes. While the Vietoris-Rips complex is simple to compute and is a good vehicle for extracting topology of sampled spaces, its size is huge--particularly in high dimensions. The witness complex on the other hand enjoys a smaller size because of a subsampling, but fails to capture the topology in high dimensions unless imposed with extra structures. We investigate a complex called the {em graph induced complex} that, to some extent, enjoys the advantages of both. It works on a subsample but still retains the power of capturing the topology as the Vietoris-Rips complex. It only needs a graph connecting the original sample points from which it builds a complex on the subsample thus taming the size considerably. We show that, using the graph induced complex one can (i) infer the one dimensional homology of a manifold from a very lean subsample, (ii) reconstruct a surface in three dimension from a sparse subsample without computing Delaunay triangulations, (iii) infer the persistent homology groups of compact sets from a sufficiently dense sample. We provide experimental evidences in support of our theory.
We construct mass deformed SU(N) L-BLG theory together with $U(M-N)_k$ Chern-Simons theory. This mass deformed L-BLG theory is a low energy world volume theory of a stack of $N$ number of M2-brane far away from $C^4/Z_k$ singularity. We carry out thi
s by defining a special scaling limit of the fields of this theory and simultaneously sending the Chern-Simons level to infinity.
Algorithms for persistent homology and zigzag persistent homology are well-studied for persistence modules where homomorphisms are induced by inclusion maps. In this paper, we propose a practical algorithm for computing persistence under $mathbb{Z}_2
$ coefficients for a sequence of general simplicial maps and show how these maps arise naturally in some applications of topological data analysis. First, we observe that it is not hard to simulate simplicial maps by inclusion maps but not necessarily in a monotone direction. This, combined with the known algorithms for zigzag persistence, provides an algorithm for computing the persistence induced by simplicial maps. Our main result is that the above simple minded approach can be improved for a sequence of simplicial maps given in a monotone direction. A simplicial map can be decomposed into a set of elementary inclusions and vertex collapses--two atomic operations that can be supported efficiently with the notion of simplex annotations for computing persistent homology. A consistent annotation through these atomic operations implies the maintenance of a consistent cohomology basis, hence a homology basis by duality. While the idea of maintaining a cohomology basis through an inclusion is not new, maintaining them through a vertex collapse is new, which constitutes an important atomic operation for simulating simplicial maps. Annotations support the vertex collapse in addition to the usual inclusion quite naturally. Finally, we exhibit an application of this new tool in which we approximate the persistence diagram of a filtration of Rips complexes where vertex collapses are used to tame the blow-up in size.
We consider the problem of finding optimal, fair and distributed power-rate strategies to achieve the sum capacity of the Gaussian multiple-access block-fading channel. In here, the transmitters have access to only their own fading coefficients, whil
e the receiver has global access to all the fading coefficients. Outage is not permitted in any communication block. The resulting average sum-throughput is also known as `power-controlled adaptive sum-capacity, which appears as an open problem in literature. This paper presents the power-controlled adaptive sum-capacity of a wide-class of popular MAC models. In particular, we propose a power-rate strategy in the presence of distributed channel state information (CSI), which is throughput optimal when all the users have identical channel statistics. The proposed scheme also has an efficient implementation using successive cancellation and rate-splitting. We propose an upperbound when the channel laws are not identical. Furthermore, the optimal schemes are extended to situations in which each transmitter has additional finite-rate partial CSI on the link quality of others.
We generalize the operators of ABJM theory, given by Schur polynomials, in ABJ theory by computing the two point functions in the free field and at finite $(N_1,N_2)$ limits. These polynomials are then identified with the states of the dual gravity t
heory. Further, we compute correlators among giant gravitons as well as between giant gravitons and ordinary gravitons through the corresponding correlators of ABJ(M) theory. Finally, we consider a particular non-trivial background produced by an operator with an $cal R$-charge of $O(N^2)$ and find, in presence of this background, due to the contribution of the non-planar corrections, the large $(N_1,N_2)$ expansion is replaced by $1/(N_1+M)$ and $1/(N_2+M)$ respectively.
We construct a class of operators, given by Schur polynomials, in ABJM theory. By computing two point functions at finite $N$ we confirm these are diagonal for this class of operators in the free field limit. We also calculate exact three and multi p
oint correlators in the zero coupling limit. Finally, we consider a particular nontrivial background produced by an operator with an $R$-charge of $O(N^2$. We show that the nonplanar corrections (which can no longer be neglected, even at large $N$) can be resummed to give a $1/(N+M)$ expansion for correlators computed in this background.
The problem of computing the anomalous dimensions of a class of (nearly) half-BPS operators with a large R-charge is reduced to the problem of diagonalizing a Cuntz oscillator chain. Due to the large dimension of the operators we consider, non-planar
corrections must be summed to correctly construct the Cuntz oscillator dynamics. These non-planar corrections do not represent quantum corrections in the dual gravitational theory, but rather, they account for the backreaction from the heavy operator whose dimension we study. Non-planar corrections accounting for quantum corrections seem to spoil integrability, in general. It is interesting to ask if non-planar corrections that account for the backreaction also spoil integrability. We find a limit in which our Cuntz chain continues to admit extra conserved charges suggesting that integrability might survive.
We propose an effective model of strongly coupled gauge theory at finite temperature on $R^3$ in the presence of an infrared cutoff. It is constructed by considering the theory on $S^3$ with an infrared cutoff and then taking the size of the $S^3$ to
infinity while keeping the cutoff fixed. This model reproduces various qualitative features expected from its gravity dual.
