Abstract:
Dense hard-particle packings are intimately related to the structure of low-temperature phases of matter and are useful models of heterogeneous materials and granular media. Most studies of the densest packings in three dimensions have considered spherical shapes, and it is only more recently that nonspherical shapes (e.g., ellipsoids) have been investigated. Superballs (whose shapes are defined by |x1|^2p + |x2|^2p + |x3|^2p <= 1) provide a versatile family of convex particles (p >= 0.5) with both cubic- and octahedral-like shapes as well as concave particles (0 < p < 0.5) with octahedral-like shapes. In this paper, we provide analytical constructions for the densest known superball packings for all convex and concave cases. The candidate maximally dense packings are certain families of Bravais lattice packings. The maximal packing density as a function of p is nonanalytic at the sphere-point (p = 1) and increases dramatically as p moves away from unity. The packing characteristics determined by the broken rotational symmetry of superballs are similar to but richer than their two-dimensional "superdisk" counterparts, and are distinctly different from that of ellipsoid packings. Our candidate optimal superball packings provide a starting point to quantify the equilibrium phase behavior of superball systems, which should deepen our understanding of the statistical thermodynamics of nonspherical-particle systems.

Abstract:
The smallest three hyperbolic compact arithmetic 5-orbifolds can be derived from two compact Coxeter polytops which are combinatorially simplicial prisms (or complete orthoschemes of degree $d=1$) in the five dimensional hyperbolic space $\mathbf{H}^5$ (see \cite{BE} and \cite{EK}). The corresponding hyperbolic tilings are generated by reflections through their delimiting hyperplanes those involve the study of the relating densest hyperball (hypersphere) packings with congruent hyperballs. The analogous problem was discussed in \cite{Sz06-1} and \cite{Sz06-2} in the hyperbolic spaces $\mathbf{H}^n$ $(n=3,4)$. In this paper we extend this procedure to determine the optimal hyperball packings to the above 5-dimensional prism tilings. We compute their metric data and the densities of their optimal hyperball packings, moreover, we formulate a conjecture for the candidate of the densest hyperball packings in the 5-dimensional hyperbolic space $\mathbf{H}^5$.

Abstract:
A remarkable coincidence has led to the discovery of a family of packings of (m^2+m-2) m/2-dimensional subspaces of m-dimensional space, whenever m is a power of 2. These packings meet the ``orthoplex bound'' and are therefore optimal.

Abstract:
This paper considers the matrix completion problem. We show that it is not necessary to assume joint incoherence, which is a standard but unintuitive and restrictive condition that is imposed by previous studies. This leads to a sample complexity bound that is order-wise optimal with respect to the incoherence parameter (as well as to the rank $r$ and the matrix dimension $n$ up to a log factor). As a consequence, we improve the sample complexity of recovering a semidefinite matrix from $O(nr^{2}\log^{2}n)$ to $O(nr\log^{2}n)$, and the highest allowable rank from $\Theta(\sqrt{n}/\log n)$ to $\Theta(n/\log^{2}n)$. The key step in proof is to obtain new bounds on the $\ell_{\infty,2}$-norm, defined as the maximum of the row and column norms of a matrix. To illustrate the applicability of our techniques, we discuss extensions to SVD projection, structured matrix completion and semi-supervised clustering, for which we provide order-wise improvements over existing results. Finally, we turn to the closely-related problem of low-rank-plus-sparse matrix decomposition. We show that the joint incoherence condition is unavoidable here for polynomial-time algorithms conditioned on the Planted Clique conjecture. This means it is intractable in general to separate a rank-$\omega(\sqrt{n})$ positive semidefinite matrix and a sparse matrix. Interestingly, our results show that the standard and joint incoherence conditions are associated respectively with the information (statistical) and computational aspects of the matrix decomposition problem.

Abstract:
We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason - the problem of "super resolution of images." We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.

Abstract:
Optimal partitioned cyclic difference packings (PCDPs) are shown to give rise to optimal frequency-hopping sequences and optimal comma-free codes. New constructions for PCDPs, based on almost difference sets and cyclic difference matrices, are given. These produce new infinite families of optimal PCDPs (and hence optimal frequency-hopping sequences and optimal comma-free codes). The existence problem for optimal PCDPs in ${\mathbb Z}_{3m}$, with $m$ base blocks of size three, is also solved for all $m\not\equiv 8,16\pmod{24}$.

Abstract:
Biclustering structures in data matrices were first formalized in a seminal paper by John Hartigan (1972) where one seeks to cluster cases and variables simultaneously. Such structures are also prevalent in block modeling of networks. In this paper, we develop a unified theory for the estimation and completion of matrices with biclustering structures, where the data is a partially observed and noise contaminated data matrix with a certain biclustering structure. In particular, we show that a constrained least squares estimator achieves minimax rate-optimal performance in several of the most important scenarios. To this end, we derive unified high probability upper bounds for all sub-Gaussian data and also provide matching minimax lower bounds in both Gaussian and binary cases. Due to the close connection of graphon to stochastic block models, an immediate consequence of our general results is a minimax rate-optimal estimator for sparse graphons.

Abstract:
We consider the matrix completion problem under a form of row/column weighted entrywise sampling, including the case of uniform entrywise sampling as a special case. We analyze the associated random observation operator, and prove that with high probability, it satisfies a form of restricted strong convexity with respect to weighted Frobenius norm. Using this property, we obtain as corollaries a number of error bounds on matrix completion in the weighted Frobenius norm under noisy sampling and for both exact and near low-rank matrices. Our results are based on measures of the "spikiness" and "low-rankness" of matrices that are less restrictive than the incoherence conditions imposed in previous work. Our technique involves an $M$-estimator that includes controls on both the rank and spikiness of the solution, and we establish non-asymptotic error bounds in weighted Frobenius norm for recovering matrices lying with $\ell_q$-"balls" of bounded spikiness. Using information-theoretic methods, we show that no algorithm can achieve better estimates (up to a logarithmic factor) over these same sets, showing that our conditions on matrices and associated rates are essentially optimal.

Abstract:
The problem of finding the asymptotic behavior of the maximal density of sphere packings in high Euclidean dimensions is one of the most fascinating and challenging problems in discrete geometry. One century ago, Minkowski obtained a rigorous lower bound that is controlled asymptotically by $1/2^d$, where $d$ is the Euclidean space dimension. An indication of the difficulty of the problem can be garnered from the fact that exponential improvement of Minkowski's bound has proved to be elusive, even though existing upper bounds suggest that such improvement should be possible. Using a statistical-mechanical procedure to optimize the density associated with a "test" pair correlation function and a conjecture concerning the existence of disordered sphere packings [S. Torquato and F. H. Stillinger, Experimental Math. {\bf 15}, 307 (2006)], the putative exponential improvement was found with an asymptotic behavior controlled by $1/2^{(0.77865...)d}$. Using the same methods, we investigate whether this exponential improvement can be further improved by exploring other test pair correlation functions correponding to disordered packings. We demonstrate that there are simpler test functions that lead to the same asymptotic result. More importantly, we show that there is a wide class of test functions that lead to precisely the same exponential improvement and therefore the asymptotic form $1/2^{(0.77865...)d}$ is much more general than previously surmised.

Abstract:
Sphere packings in high dimensions interest mathematicians and physicists and have direct applications in communications theory. Remarkably, no one has been able to provide exponential improvement on a 100-year-old lower bound on the maximal packing density due to Minkowski in $d$-dimensional Euclidean space $\Re^d$. The asymptotic behavior of this bound is controlled by $2^{-d}$ in high dimensions. Using an optimization procedure that we introduced earlier \cite{To02c} and a conjecture concerning the existence of disordered sphere packings in $\Re^d$, we obtain a provisional lower bound on the density whose asymptotic behavior is controlled by $2^{-0.7786... d}$, thus providing the putative exponential improvement of Minkowski's bound. The conjecture states that a hard-core nonnegative tempered distribution is a pair correlation function of a translationally invariant disordered sphere packing in $\Re^d$ for asymptotically large d if and only if the Fourier transform of the autocovariance function is nonnegative. The conjecture is supported by two explicit analytically characterized disordered packings, numerical simulations in low dimensions, known necessary conditions that only have relevance in very low dimensions, and the fact that we can recover the forms of known rigorous lower bounds. A byproduct of our approach is an asymptotic lower bound on the average kissing number whose behavior is controlled by $2^{0.2213... d}$, which is to be compared to the best known asymptotic lower bound on the individual kissing number of $2^{0.2075... d}$. Interestingly, our optimization procedure is precisely the dual of a primal linear program devised by Cohn and Elkies \cite{Co03} to obtain upper bounds on the density, and hence has implications for linear programming bounds.