Abstract A well-known open problem of Meir and Moser asks if the squares of sidelength 1/n for $$n\ge 2$$ n ≥ 2 can be packed perfectly into a rectangle of area $$\sum _{n=2}^\infty n^{-2}=\pi ^2/6-1$$ ∑ n = 2 ∞ n - 2 = π 2 / 6 - 1 . In this paper we show that for any $$1/2 1 / 2 < t < 1 , and any $$n_0$$ n 0 that is sufficiently large depending on t, the squares of sidelength $$n^{-t}$$ n - t for $$n\ge n_0$$ n ≥ n 0 can be packed perfectly into a square of area $$\sum _{n=n_0}^\infty n^{-2t}$$ ∑ n = n 0 ∞ n - 2 t . This was previously known (if one packs a rectangle instead of a square) for $$1/2 1 / 2 < t ≤ 2 / 3 (in which case one can take $$n_0=1$$ n 0 = 1 ).

Abstract We construct an example of a group $$G = \mathbb {Z}^2 \times G_0$$ G=Z2×G0 for a finite abelian group $$G_0$$ G0 , a subsetEof $$G_0$$ G0 , and two finite subsets $$F_1,F_2$$ F1,F2 of G, such that it is undecidable in ZFC whether $$\mathbb {Z}^2\times E$$ Z2×E can be tiled by translations of $$F_1,F_2$$ F1,F2 . In particular, this implies that this tiling problem isaperiodic, in the sense that (in the standard universe of ZFC) there exist translational tilings ofEby the tiles $$F_1,F_2$$ F1,F2 , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in $$\mathbb {Z}^2$$ Z2 ). A similar construction also applies for $$G=\mathbb {Z}^d$$ G=Zd for sufficiently large d. If one allows the group $$G_0$$ G0 to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile F. The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.

This paper is concerned with the problem of recovering an unknown matrix from a small fraction of its entries. This is known as thematrix completionproblem, and comes up in a great number of applications, including the famousNetflix Prizeand other similar questions in collaborative filtering. In general, accurate recovery of a matrix from a small number of entries is impossible, but the knowledge that the unknown matrix has low rank radically changes this premise, making the search for solutions meaningful. This paper presents optimality results quantifying the minimum number of entries needed to recover a matrix of rankrexactly by any method whatsoever (the information theoretic limit). More importantly, the paper shows that, under certain incoherence assumptions on the singular vectors of the matrix, recovery is possible by solving a convenient convex program as soon as the number of entries is on the order of the information theoretic limit (up to logarithmic factors). This convex program simply finds, among all matrices consistent with the observed entries, that with minimum nuclear norm. As an example, we show that on the order ofnrlog(n) samples are needed to recover a randomnxnmatrix of rankrby any method, and to be sure, nuclear norm minimization succeeds as soon as the number of entries is of the formnrpolylog(n).

Combinatorics, like computer science, often has to deal with large objects of unspecified (or unusable) structure. One powerful way to deal with such an arbitrary object is to decompose it into more usable components. In particular, it has proven profitable to decompose such objects into a structured component, a pseudo-random component, and a small component (i.e. an error term): in many cases it is the structured component which then dominates. We illustrate this philosophy in a number of model cases.

Let M be an arbitrary n by n matrix. We study the conditionnumber a random perturbation M+Nn of M, where Nn is arandom matrix. It is shown that, under very general conditions on M and Mn, the condition number of M+Nn is polynomial in nwith very high probability. The main novelty here is that we allow Nn to have discrete distribution.

This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f/spl isin/C/sup N/ and a randomly chosen set of frequencies /spl Omega/. Is it possible to reconstruct f from the partial knowledge of its Fourier coefficients on the set /spl Omega/? A typical result of this paper is as follows. Suppose that f is a superposition of |T| spikes f(t)=/spl sigma//sub /spl tau//spl isin/T/f(/spl tau/)/spl delta/(t-/spl tau/) obeying |T|/spl les/C/sub M//spl middot/(log N)/sup -1/ /spl middot/ |/spl Omega/| for some constant C/sub M/>0. We do not know the locations of the spikes nor their amplitudes. Then with probability at least 1-O(N/sup -M/), f can be reconstructed exactly as the solution to the /spl lscr//sub 1/ minimization problem. In short, exact recovery may be obtained by solving a convex optimization problem. We give numerical values for C/sub M/ which depend on the desired probability of success. Our result may be interpreted as a novel kind of nonlinear sampling theorem. In effect, it says that any signal made out of |T| spikes may be recovered by convex programming from almost every set of frequencies of size O(|T|/spl middot/logN). Moreover, this is nearly optimal in the sense that any method succeeding with probability 1-O(N/sup -M/) would in general require a number of frequency samples at least proportional to |T|/spl middot/logN. The methodology extends to a variety of other situations and higher dimensions. For example, we show how one can reconstruct a piecewise constant (one- or two-dimensional) object from incomplete frequency samples - provided that the number of jumps (discontinuities) obeys the condition above - by minimizing other convex functionals such as the total variation of f.

Suppose we are given a vector $f$ in a class ${\cal F} \subset{\BBR}^N$ , e.g., a class of digital signals or digital images. How many linear measurements do we need to make about $f$ to be able to recover $f$ to within precision $\epsilon$ in the Euclidean $(\ell_2)$ metric? This paper shows that if the objects of interest are sparse in a fixed basis or compressible, then it is possible to reconstruct $f$ to within very high accuracy from a small number of random measurements by solving a simple linear program. More precisely, suppose that the $n$ th largest entry of the vector $\vert f\vert$ (or of its coefficients in a fixed basis) obeys $\vert f\vert _{(n)} \le R \cdot n^{-1/p}$ , where $R > 0$ and $p > 0$ . Suppose that we take measurements $y_k = \langle f, X_k\rangle, k = 1, \ldots, K$ , where the $X_k$ are $N$ -dimensional Gaussian vectors with independent standard normal entries. Then for each $f$ obeying the decay estimate above for some $0 < p < 1$ and with overwhelming probability, our reconstruction $f^\sharp$ , defined as the solution to the constraints $y_k = \langle f^\sharp, X_k \rangle$ with minimal $\ell_1$ norm, obeys $$ \Vert f - f^\sharp\Vert _{\ell_2} \le C_p \cdot R \cdot (K/\log N)^{-r}, \quad r = 1/p - 1/2. $$ There is a sense in which this result is optimal; it is generally impossible to obtain a higher accuracy from any set of $K$ measurements whatsoever. The methodology extends to various other random measurement ensembles; for example, we show that similar results hold if one observes a few randomly sampled Fourier coefficients of $f$ . In fact, the results are quite general and require only two hypotheses on the measurement ensemble which are detailed.

Suppose we wish to transmit a vector f ϵ Rnreliably. A frequently discussed approach consists in encoding f with an m by n coding matrix A. Assume now that a fraction of the entries of Af are corrupted in a completely arbitrary fashion by an error e. We do not know which entries are affected nor do we know how they are affected. Is it possible to recover f exactly from the corrupted m-dimensional vector y = Af + e?

We proved several results concerning the determinant of a random pm 1 matrix. In particular, we show that with high probability, the determinant has absolute value very close to √n!.

This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e. Here, A is an m by n (coding) matrix and e is an arbitrary and unknown vector of errors. Is it possible to recover f exactly from the data y? We prove that under suitable conditions on the coding matrix A, the input f is the unique solution to the /spl lscr//sub 1/-minimization problem (/spl par/x/spl par//sub /spl lscr/1/:=/spl Sigma//sub i/|x/sub i/|) min(g/spl isin/R/sup n/) /spl par/y - Ag/spl par//sub /spl lscr/1/ provided that the support of the vector of errors is not too large, /spl par/e/spl par//sub /spl lscr/0/:=|{i:e/sub i/ /spl ne/ 0}|/spl les//spl rho//spl middot/m for some /spl rho/>0. In short, f can be recovered exactly by solving a simple convex optimization problem (which one can recast as a linear program). In addition, numerical experiments suggest that this recovery procedure works unreasonably well; f is recovered exactly even in situations where a significant fraction of the output is corrupted. This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. There are also significant connections with the problem of recovering signals from highly incomplete measurements. In fact, the results introduced in this paper improve on our earlier work. Finally, underlying the success of /spl lscr//sub 1/ is a crucial property we call the uniform uncertainty principle that we shall describe in detail.