BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

John Wright

John Wright appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Machine LearningInformation Theorymath.ITComputer VisionComputational Complexitymath.OCquant-phData Structures and Algorithmscond-mat.mtrl-sciphysics.atom-phApplicationsastro-ph.COastro-ph.HEastro-ph.IMastro-ph.SRComputational Geometrycond-mat.supr-coneess.IVgr-qc

Catalog footprint

What is connected

34works
19topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

34 published item(s)

preprint2022arXiv

From Symmetry to Geometry: Tractable Nonconvex Problems

As science and engineering have become increasingly data-driven, the role of optimization has expanded to touch almost every stage of the data analysis pipeline, from signal and data acquisition to modeling and prediction. The optimization problems encountered in practice are often nonconvex. While challenges vary from problem to problem, one common source of nonconvexity is nonlinearity in the data or measurement model. Nonlinear models often exhibit symmetries, creating complicated, nonconvex objective landscapes, with multiple equivalent solutions. Nevertheless, simple methods (e.g., gradient descent) often perform surprisingly well in practice. The goal of this survey is to highlight a class of tractable nonconvex problems, which can be understood through the lens of symmetries. These problems exhibit a characteristic geometric structure: local minimizers are symmetric copies of a single "ground truth" solution, while other critical points occur at balanced superpositions of symmetric copies of the ground truth, and exhibit negative curvature in directions that break the symmetry. This structure enables efficient methods to obtain global minimizers. We discuss examples of this phenomenon arising from a wide range of problems in imaging, signal processing, and data analysis. We highlight the key role of symmetry in shaping the objective landscape and discuss the different roles of rotational and discrete symmetries. This area is rich with observed phenomena and open problems; we close by highlighting directions for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Generalized Approach to Matched Filtering using Neural Networks

Gravitational wave science is a pioneering field with rapidly evolving data analysis methodology currently assimilating and inventing deep learning techniques. The bulk of the sophisticated flagship searches of the field rely on the time-tested matched filtering principle within their core. In this paper, we make a key observation on the relationship between the emerging deep learning and the traditional techniques: matched filtering is formally equivalent to a particular neural network. This means that a neural network can be constructed analytically to exactly implement matched filtering, and can be further trained on data or boosted with additional complexity for improved performance. Moreover, we show that the proposed neural network architecture can outperform matched filtering, both with or without knowledge of a prior on the parameter distribution. When a prior is given, the proposed neural network can approach the statistically optimal performance. We also propose and investigate two different neural network architectures MNet-Shallow and MNet-Deep, both of which implement matched filtering at initialization and can be trained on data. MNet-Shallow has simpler structure, while MNet-Deep is more flexible and can deal with a wider range of distributions. Our theoretical findings are corroborated by experiments using real LIGO data and synthetic injections, where our proposed methods significantly outperform matched filtering at false positive rates above $5\times 10^{-3}\%$. The fundamental equivalence between matched filtering and neural networks allows us to define a "complexity standard candle" to characterize the relative complexity of the different approaches to gravitational wave signal searches in a common framework. Finally, our results suggest new perspectives on the role of deep learning in gravitational wave detection.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Resource-Efficient Invariant Networks: Exponential Gains by Unrolled Optimization

Achieving invariance to nuisance transformations is a fundamental challenge in the construction of robust and reliable vision systems. Existing approaches to invariance scale exponentially with the dimension of the family of transformations, making them unable to cope with natural variabilities in visual data such as changes in pose and perspective. We identify a common limitation of these approaches--they rely on sampling to traverse the high-dimensional space of transformations--and propose a new computational primitive for building invariant networks based instead on optimization, which in many scenarios provides a provably more efficient method for high-dimensional exploration than sampling. We provide empirical and theoretical corroboration of the efficiency gains and soundness of our proposed method, and demonstrate its utility in constructing an efficient invariant network for a simple hierarchical object detection task when combined with unrolled optimization. Code for our networks and experiments is available at https://github.com/sdbuch/refine.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Testing matrix product states

Devising schemes for testing the amount of entanglement in quantum systems has played a crucial role in quantum computing and information theory. Here, we study the problem of testing whether an unknown state $|ψ\rangle$ is a matrix product state (MPS) in the property testing model. MPS are a class of physically-relevant quantum states which arise in the study of quantum many-body systems. A quantum state $|ψ_{1,...,n}\rangle$ comprised of $n$ qudits is said to be an MPS of bond dimension $r$ if the reduced density matrix $ψ_{1,...,k}$ has rank $r$ for each $k \in \{1,...,n\}$. When $r=1$, this corresponds to the set of product states. For larger values of $r$, this yields a more expressive class of quantum states, which are allowed to possess limited amounts of entanglement. In the property testing model, one is given $m$ identical copies of $|ψ\rangle$, and the goal is to determine whether $|ψ\rangle$ is an MPS of bond dimension $r$ or whether $|ψ\rangle$ is far from all such states. For the case of product states, we study the product test, a simple two-copy test previously analyzed by Harrow and Montanaro (FOCS 2010), and a key ingredient in their proof that $\mathsf{QMA(2)}=\mathsf{QMA}(k)$ for $k \geq 2$. We give a new and simpler analysis of the product test which achieves an optimal bound for a wide range of parameters, answering open problems of Harrow and Montanaro (FOCS 2010) and Montanaro and de Wolf (2016). For the case of $r\geq 2$, we give an efficient algorithm for testing whether $|ψ\rangle$ is an MPS of bond dimension $r$ using $m = O(n r^2)$ copies, independent of the dimensions of the qudits, and we show that $Ω(n^{1/2})$ copies are necessary for this task. This lower bound shows that a dependence on the number of qudits $n$ is necessary, in sharp contrast to the case of product states where a constant number of copies suffices.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An unexplored MBE growth mode reveals new properties of superconducting NbN

Accessing unexplored conditions in crystal growth often reveals remarkable surprises and new regimes of physical behavior. In this work, performing molecular beam epitaxy of the technologically important superconductor NbN at temperatures greater than 1000$^\circ$C, higher than in the past, is found to reveal persistent RHEED oscillations throughout the growth, atomically smooth surfaces, normal metal resistivities as low as 37$μΩ$-cm and superconducting critical temperatures in excess of 15 K. Most remarkably, a reversal of the sign of the Hall coefficient is observed as the NbN films are cooled, and the high material quality allows the first imaging of Abrikosov vortex lattices in this superconductor.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications

The problem of finding the sparsest vector (direction) in a low dimensional subspace can be considered as a homogeneous variant of the sparse recovery problem, which finds applications in robust subspace recovery, dictionary learning, sparse blind deconvolution, and many other problems in signal processing and machine learning. However, in contrast to the classical sparse recovery problem, the most natural formulation for finding the sparsest vector in a subspace is usually nonconvex. In this paper, we overview recent advances on global nonconvex optimization theory for solving this problem, ranging from geometric analysis of its optimization landscapes, to efficient optimization algorithms for solving the associated nonconvex optimization problem, to applications in machine intelligence, representation learning, and imaging sciences. Finally, we conclude this review by pointing out several interesting open problems for future research.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Molecular Beam Epitaxy Growth of Scandium Nitride on Hexagonal SiC, GaN, and AlN

RF plasma assisted MBE growth of Scandium Nitride (ScN) thin films on GaN (0001)/SiC, AlN (0001)/Al2O3 and on 6H-SiC (0001) hexagonal substrates is found to lead to a face centered cubic (rock-salt) crystal structure with (111) out-of-plane orientation instead of hexagonal orientation. For the first time, cubic (111) twinned patterns in ScN are observed by in-situ electron diffraction during epitaxy, and the twin domains in ScN are detected by electron backscattered diffraction, and further corroborated with X-ray diffraction. The epitaxial ScN films display very smooth, sub nanometer surface roughness at a growth temperature of 750C. Temperature-dependent Hall-effect measurements indicate a constant high n-type carrier concentration of ~1x1020/cm3 and electron mobilities of ~ 20 cm2/Vs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Efficient quantum tomography II

Following [OW16], we continue our analysis of: (1) "Quantum tomography", i.e., learning a quantum state, i.e., the quantum generalization of learning a discrete probability distribution; (2) The distribution of Young diagrams output by the RSK algorithm on random words. Regarding (2), we introduce two powerful new tools: (i) A precise upper bound on the expected length of the longest union of $k$ disjoint increasing subsequences in a random length-$n$ word with letter distribution $α_1 \geq α_2 \geq \cdots \geq α_d$; (ii) A new majorization property of the RSK algorithm that allows one to analyze the Young diagram formed by the lower rows $λ_k, λ_{k+1}, \dots$ of its output. These tools allow us to prove several new theorems concerning the distribution of random Young diagrams in the nonasymptotic regime, giving concrete error bounds that are optimal, or nearly so, in all parameters. As one example, we give a fundamentally new proof of the fact that the expected length of the longest increasing sequence in a random length-$n$ permutation is bounded by $2\sqrt{n}$. This is the $k = 1$, $α_i \equiv \frac1d$, $d \to \infty$ special case of a much more general result we prove: the expected length of the $k$th Young diagram row produced by an $α$-random word is $α_k n \pm 2\sqrt{α_kd n}$. From our new analyses of random Young diagrams we derive several new results in quantum tomography, including: (i) Learning the eigenvalues of an unknown state to $ε$-accuracy in Hellinger-squared, chi-squared, or KL distance, using $n = O(d^2/ε)$ copies; (ii) Learning the optimal rank-$k$ approximation of an unknown state to $ε$-fidelity (Hellinger-squared distance) using $n = \widetilde{O}(kd/ε)$ copies.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Finding a sparse vector in a subspace: Linear sparsity using alternating directions

Is it possible to find the sparsest vector (direction) in a generic subspace $\mathcal{S} \subseteq \mathbb{R}^p$ with $\mathrm{dim}(\mathcal{S})= n < p$? This problem can be considered a homogeneous variant of the sparse recovery problem, and finds connections to sparse dictionary learning, sparse PCA, and many other problems in signal processing and machine learning. In this paper, we focus on a **planted sparse model** for the subspace: the target sparse vector is embedded in an otherwise random subspace. Simple convex heuristics for this planted recovery problem provably break down when the fraction of nonzero entries in the target sparse vector substantially exceeds $O(1/\sqrt{n})$. In contrast, we exhibit a relatively simple nonconvex approach based on alternating directions, which provably succeeds even when the fraction of nonzero entries is $Ω(1)$. To the best of our knowledge, this is the first practical algorithm to achieve linear scaling under the planted sparse model. Empirically, our proposed algorithm also succeeds in more challenging data models, e.g., sparse dictionary learning.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

When Are Nonconvex Problems Not Scary?

In this note, we focus on smooth nonconvex optimization problems that obey: (1) all local minimizers are also global; and (2) around any saddle point or local maximizer, the objective has a negative directional curvature. Concrete applications such as dictionary learning, generalized phase retrieval, and orthogonal tensor decomposition are known to induce such structures. We describe a second-order trust-region algorithm that provably converges to a global minimizer efficiently, without special initializations. Finally we highlight alternatives, and open problems in this direction.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A Batchwise Monotone Algorithm for Dictionary Learning

We propose a batchwise monotone algorithm for dictionary learning. Unlike the state-of-the-art dictionary learning algorithms which impose sparsity constraints on a sample-by-sample basis, we instead treat the samples as a batch, and impose the sparsity constraint on the whole. The benefit of batchwise optimization is that the non-zeros can be better allocated across the samples, leading to a better approximation of the whole. To accomplish this, we propose procedures to switch non-zeros in both rows and columns in the support of the coefficient matrix to reduce the reconstruction error. We prove in the proposed support switching procedure the objective of the algorithm, i.e., the reconstruction error, decreases monotonically and converges. Furthermore, we introduce a block orthogonal matching pursuit algorithm that also operates on sample batches to provide a warm start. Experiments on both natural image patches and UCI data sets show that the proposed algorithm produces a better approximation with the same sparsity levels compared to the state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Beating the random assignment on constraint satisfaction problems of bounded degree

We show that for any odd $k$ and any instance of the Max-kXOR constraint satisfaction problem, there is an efficient algorithm that finds an assignment satisfying at least a $\frac{1}{2} + Ω(1/\sqrt{D})$ fraction of constraints, where $D$ is a bound on the number of constraints that each variable occurs in. This improves both qualitatively and quantitatively on the recent work of Farhi, Goldstone, and Gutmann (2014), which gave a \emph{quantum} algorithm to find an assignment satisfying a $\frac{1}{2} + Ω(D^{-3/4})$ fraction of the equations. For arbitrary constraint satisfaction problems, we give a similar result for "triangle-free" instances; i.e., an efficient algorithm that finds an assignment satisfying at least a $μ+ Ω(1/\sqrt{D})$ fraction of constraints, where $μ$ is the fraction that would be satisfied by a uniformly random assignment.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Complete Dictionary Recovery over the Sphere

We consider the problem of recovering a complete (i.e., square and invertible) matrix $\mathbf A_0$, from $\mathbf Y \in \mathbb R^{n \times p}$ with $\mathbf Y = \mathbf A_0 \mathbf X_0$, provided $\mathbf X_0$ is sufficiently sparse. This recovery problem is central to the theoretical understanding of dictionary learning, which seeks a sparse representation for a collection of input signals, and finds numerous applications in modern signal processing and machine learning. We give the first efficient algorithm that provably recovers $\mathbf A_0$ when $\mathbf X_0$ has $O(n)$ nonzeros per column, under suitable probability model for $\mathbf X_0$. In contrast, prior results based on efficient algorithms provide recovery guarantees when $\mathbf X_0$ has only $O(n^{1-δ})$ nonzeros per column for any constant $δ\in (0, 1)$. Our algorithmic pipeline centers around solving a certain nonconvex optimization problem with a spherical constraint, and hence is naturally phrased in the language of manifold optimization. To show this apparently hard problem is tractable, we first provide a geometric characterization of the high-dimensional objective landscape, which shows that with high probability there are no "spurious" local minima. This particular geometric structure allows us to design a Riemannian trust region algorithm over the sphere that provably converges to one local minimizer with an arbitrary initialization, despite the presence of saddle points. The geometric approach we develop here may also shed light on other problems arising from nonconvex recovery of structured signals.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Efficient quantum tomography

In the quantum state tomography problem, one wishes to estimate an unknown $d$-dimensional mixed quantum state $ρ$, given few copies. We show that $O(d/ε)$ copies suffice to obtain an estimate $\hatρ$ that satisfies $\|\hatρ - ρ\|_F^2 \leq ε$ (with high probability). An immediate consequence is that $O(\mathrm{rank}(ρ) \cdot d/ε^2) \leq O(d^2/ε^2)$ copies suffice to obtain an $ε$-accurate estimate in the standard trace distance. This improves on the best known prior result of $O(d^3/ε^2)$ copies for full tomography, and even on the best known prior result of $O(d^2\log(d/ε)/ε^2)$ copies for spectrum estimation. Our result is the first to show that nontrivial tomography can be obtained using a number of copies that is just linear in the dimension. Next, we generalize these results to show that one can perform efficient principal component analysis on $ρ$. Our main result is that $O(k d/ε^2)$ copies suffice to output a rank-$k$ approximation $\hatρ$ whose trace distance error is at most $ε$ more than that of the best rank-$k$ approximator to $ρ$. This subsumes our above trace distance tomography result and generalizes it to the case when $ρ$ is not guaranteed to be of low rank. A key part of the proof is the analogous generalization of our spectrum-learning results: we show that the largest $k$ eigenvalues of $ρ$ can be estimated to trace-distance error $ε$ using $O(k^2/ε^2)$ copies. In turn, this result relies on a new coupling theorem concerning the Robinson-Schensted-Knuth algorithm that should be of independent combinatorial interest.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Improved and Simplified Inapproximability for k-means

The k-means problem consists of finding k centers in the d-dimensional Euclidean space that minimize the sum of the squared distances of all points in an input set P to their closest respective center. Awasthi et. al. recently showed that there exists a constant c > 1 such that it is NP-hard to approximate the k-means objective within a factor of c. We establish that the constant c is at least 1.0013.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Quantum Spectrum Testing

In this work, we study the problem of testing properties of the spectrum of a mixed quantum state. Here one is given $n$ copies of a mixed state $ρ\in\mathbb{C}^{d\times d}$ and the goal is to distinguish whether $ρ$'s spectrum satisfies some property $\mathcal{P}$ or is at least $ε$-far in $\ell_1$-distance from satisfying $\mathcal{P}$. This problem was promoted in the survey of Montanaro and de Wolf under the name of testing unitarily invariant properties of mixed states. It is the natural quantum analogue of the classical problem of testing symmetric properties of probability distributions. Here, the hope is for algorithms with subquadratic copy complexity in the dimension $d$. This is because the "empirical Young diagram (EYD) algorithm" can estimate the spectrum of a mixed state up to $ε$-accuracy using only $\widetilde{O}(d^2/ε^2)$ copies. In this work, we show that given a mixed state $ρ\in\mathbb{C}^{d\times d}$: (i) $Θ(d/ε^2)$ copies are necessary and sufficient to test whether $ρ$ is the maximally mixed state, i.e., has spectrum $(\frac1d, ..., \frac1d)$; (ii) $Θ(r^2/ε)$ copies are necessary and sufficient to test with one-sided error whether $ρ$ has rank $r$, i.e., has at most $r$ nonzero eigenvalues; (iii) $\widetildeΘ(r^2/Δ)$ copies are necessary and sufficient to distinguish whether $ρ$ is maximally mixed on an $r$-dimensional or an $(r+Δ)$-dimensional subspace; and (iv) The EYD algorithm requires $Ω(d^2/ε^2)$ copies to estimate the spectrum of $ρ$ up to $ε$-accuracy, nearly matching the known upper bound. In addition, we simplify part of the proof of the upper bound. Our techniques involve the asymptotic representation theory of the symmetric group; in particular Kerov's algebra of polynomial functions on Young diagrams.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Absolute-Magnitude Distributions of Supernovae

The absolute-magnitude distributions of seven supernova types are presented. The data used here were primarily taken from the Asiago Supernova Catalogue, but were supplemented with additional data. We accounted for both foreground and host-galaxy extinction. A bootstrap method is used to correct the samples for Malmquist bias. Separately, we generate volume-limited samples, restricted to events within 100 Mpc. We find that the superluminous events (M_B < -21) make up only about 0.1% of all supernovae in the bias-corrected sample. The subluminous events (M_B > -15) make up about 3%. The normal Ia distribution was the brightest with a mean absolute blue magnitude of -19.25. The IIP distribution was the dimmest at -16.75.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Efficient Point-to-Subspace Query in $\ell^1$ with Application to Robust Object Instance Recognition

Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space, and a query point (image), efficiently determine the nearest subspace to the query in $\ell^1$ distance. In contrast to the naive exhaustive search which entails large-scale linear programs, we show that the computational burden can be cut down significantly by a simple two-stage algorithm: (1) projecting the query and data-base subspaces into lower-dimensional space by random Cauchy matrix, and solving small-scale distance evaluations (linear programs) in the projection space to locate candidate nearest; (2) with few candidates upon independent repetition of (1), getting back to the high-dimensional space and performing exhaustive search. To preserve the identity of the nearest subspace with nontrivial probability, the projection dimension typically is low-order polynomial of the subspace dimension multiplied by logarithm of number of the subspaces (Theorem 2.1). The reduced dimensionality and hence complexity renders the proposed algorithm particularly relevant to vision application such as robust face and object instance recognition that we investigate empirically.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Hardness of robust graph isomorphism, Lasserre gaps, and asymmetry of random graphs

Building on work of Cai, Fürer, and Immerman \cite{CFI92}, we show two hardness results for the Graph Isomorphism problem. First, we show that there are pairs of nonisomorphic $n$-vertex graphs $G$ and $H$ such that any sum-of-squares (SOS) proof of nonisomorphism requires degree $Ω(n)$. In other words, we show an $Ω(n)$-round integrality gap for the Lasserre SDP relaxation. In fact, we show this for pairs $G$ and $H$ which are not even $(1-10^{-14})$-isomorphic. (Here we say that two $n$-vertex, $m$-edge graphs $G$ and $H$ are $α$-isomorphic if there is a bijection between their vertices which preserves at least $αm$ edges.) Our second result is that under the {\sc R3XOR} Hypothesis \cite{Fei02} (and also any of a class of hypotheses which generalize the {\sc R3XOR} Hypothesis), the \emph{robust} Graph Isomorphism problem is hard. I.e.\ for every $ε> 0$, there is no efficient algorithm which can distinguish graph pairs which are $(1-ε)$-isomorphic from pairs which are not even $(1-ε_0)$-isomorphic for some universal constant $ε_0$. Along the way we prove a robust asymmetry result for random graphs and hypergraphs which may be of independent interest.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Scalable Quantum Computing Architecture with Mixed Species Ion Chains

We report on progress towards implementing mixed ion species quantum information processing for a scalable ion trap architecture. Mixed species chains may help solve several problems with scaling ion trap quantum computation to large numbers of qubits. Initial temperature measurements of linear Coulomb crystals containing barium and ytterbium ions indicate that the mass difference does not significantly impede cooling at low ion numbers. Average motional occupation numbers are estimated to be $\bar{n} \approx 130$ quanta per mode for chains with small numbers of ions, which is within a factor of three of the Doppler limit for barium ions in our trap. We also discuss generation of ion-photon entanglement with barium ions with a fidelity of $F \ge 0.84$, which is an initial step towards remote ion-ion coupling in a more scalable quantum information architecture. Further, we are working to implement these techniques in surface traps in order to exercise greater control over ion chain ordering and positioning.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

A System for Trapping Barium Ions in a Microfabricated Surface Trap

We have developed a vacuum chamber and control system for rapid testing of microfabricated surface ion traps. Our system is modular in design and is based on an in-vacuum printed circuit board with integrated filters. We have used this system to successfully trap and cool barium ions and have achieved ion 'dark' lifetimes of 31.6 s +- 3.4 s with controlled shuttling of ions. We provide a detailed description of the ion trap system including the in-vacuum materials used, control electronics and neutral atom source. We discuss the challenges presented in achieving a system which can work reliably over two years of operations in which the trap under test was changed at least 10 times.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Decision Trees, Protocols, and the Fourier Entropy-Influence Conjecture

Given $f:\{-1, 1\}^n \rightarrow \{-1, 1\}$, define the \emph{spectral distribution} of $f$ to be the distribution on subsets of $[n]$ in which the set $S$ is sampled with probability $\widehat{f}(S)^2$. Then the Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai (1996) states that there is some absolute constant $C$ such that $\operatorname{H}[\widehat{f}^2] \leq C\cdot\operatorname{Inf}[f]$. Here, $\operatorname{H}[\widehat{f}^2]$ denotes the Shannon entropy of $f$'s spectral distribution, and $\operatorname{Inf}[f]$ is the total influence of $f$. This conjecture is one of the major open problems in the analysis of Boolean functions, and settling it would have several interesting consequences. Previous results on the FEI conjecture have been largely through direct calculation. In this paper we study a natural interpretation of the conjecture, which states that there exists a communication protocol which, given subset $S$ of $[n]$ distributed as $\widehat{f}^2$, can communicate the value of $S$ using at most $C\cdot\operatorname{Inf}[f]$ bits in expectation. Using this interpretation, we are able show the following results: 1. First, if $f$ is computable by a read-$k$ decision tree, then $\operatorname{H}[\widehat{f}^2] \leq 9k\cdot \operatorname{Inf}[f]$. 2. Next, if $f$ has $\operatorname{Inf}[f] \geq 1$ and is computable by a decision tree with expected depth $d$, then $\operatorname{H}[\widehat{f}^2] \leq 12d\cdot \operatorname{Inf}[f]$. 3. Finally, we give a new proof of the main theorem of O'Donnell and Tan (ICALP 2013), i.e. that their FEI$^+$ conjecture composes. In addition, we show that natural improvements to our decision tree results would be sufficient to prove the FEI conjecture in its entirety. We believe that our methods give more illuminating proofs than previous results about the FEI conjecture.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery

Recovering a low-rank tensor from incomplete information is a recurring problem in signal processing and machine learning. The most popular convex relaxation of this problem minimizes the sum of the nuclear norms of the unfoldings of the tensor. We show that this approach can be substantially suboptimal: reliably recovering a $K$-way tensor of length $n$ and Tucker rank $r$ from Gaussian measurements requires $Ω(r n^{K-1})$ observations. In contrast, a certain (intractable) nonconvex formulation needs only $O(r^K + nrK)$ observations. We introduce a very simple, new convex relaxation, which partially bridges this gap. Our new formulation succeeds with $O(r^{\lfloor K/2 \rfloor}n^{\lceil K/2 \rceil})$ observations. While these results pertain to Gaussian measurements, simulations strongly suggest that the new norm also outperforms the sum of nuclear norms for tensor completion from a random subset of entries. Our lower bound for the sum-of-nuclear-norms model follows from a new result on recovering signals with multiple sparse structures (e.g. sparse, low rank), which perhaps surprisingly demonstrates the significant suboptimality of the commonly used recovery approach via minimizing the sum of individual sparsity inducing norms (e.g. $l_1$, nuclear norm). Our new formulation for low-rank tensor recovery however opens the possibility in reducing the sample complexity by exploiting several structures jointly.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Toward Guaranteed Illumination Models for Non-Convex Objects

Illumination variation remains a central challenge in object detection and recognition. Existing analyses of illumination variation typically pertain to convex, Lambertian objects, and guarantee quality of approximation in an average case sense. We show that it is possible to build V(vertex)-description convex cone models with worst-case performance guarantees, for non-convex Lambertian objects. Namely, a natural verification test based on the angle to the constructed cone guarantees to accept any image which is sufficiently well-approximated by an image of the object under some admissible lighting condition, and guarantees to reject any image that does not have a sufficiently good approximation. The cone models are generated by sampling point illuminations with sufficient density, which follows from a new perturbation bound for point images in the Lambertian model. As the number of point images required for guaranteed verification may be large, we introduce a new formulation for cone preserving dimensionality reduction, which leverages tools from sparse and low-rank decomposition to reduce the complexity, while controlling the approximation error with respect to the original cone.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Compressive Principal Component Pursuit

We consider the problem of recovering a target matrix that is a superposition of low-rank and sparse components, from a small set of linear measurements. This problem arises in compressed sensing of structured high-dimensional signals such as videos and hyperspectral images, as well as in the analysis of transformation invariant low-rank recovery. We analyze the performance of the natural convex heuristic for solving this problem, under the assumption that measurements are chosen uniformly at random. We prove that this heuristic exactly recovers low-rank and sparse terms, provided the number of observations exceeds the number of intrinsic degrees of freedom of the component signals by a polylogarithmic factor. Our analysis introduces several ideas that may be of independent interest for the more general problem of compressed sensing and decomposing superpositions of multiple structured signals.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Efficient Point-to-Subspace Query in $\ell^1$: Theory and Applications in Computer Vision

Motivated by vision tasks such as robust face and object recognition, we consider the following general problem: given a collection of low-dimensional linear subspaces in a high-dimensional ambient (image) space and a query point (image), efficiently determine the nearest subspace to the query in $\ell^1$ distance. We show in theory that Cauchy random embedding of the objects into significantly-lower-dimensional spaces helps preserve the identity of the nearest subspace with constant probability. This offers the possibility of efficiently selecting several candidates for accurate search. We sketch preliminary experiments on robust face and digit recognition to corroborate our theory.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Exact Recovery of Sparsely-Used Dictionaries

We consider the problem of learning sparsely used dictionaries with an arbitrary square dictionary and a random, sparse coefficient matrix. We prove that $O (n \log n)$ samples are sufficient to uniquely determine the coefficient matrix. Based on this proof, we design a polynomial-time algorithm, called Exact Recovery of Sparsely-Used Dictionaries (ER-SpUD), and prove that it probably recovers the dictionary and coefficient matrix when the coefficient matrix is sufficiently sparse. Simulation results show that ER-SpUD reveals the true dictionary as well as the coefficients with probability higher than many state-of-the-art algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Principal Component Pursuit with Reduced Linear Measurements

In this paper, we study the problem of decomposing a superposition of a low-rank matrix and a sparse matrix when a relatively few linear measurements are available. This problem arises in many data processing tasks such as aligning multiple images or rectifying regular texture, where the goal is to recover a low-rank matrix with a large fraction of corrupted entries in the presence of nonlinear domain transformation. We consider a natural convex heuristic to this problem which is a variant to the recently proposed Principal Component Pursuit. We prove that under suitable conditions, this convex program guarantees to recover the correct low-rank and sparse components despite reduced measurements. Our analysis covers both random and deterministic measurement models.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the Local Correctness of L^1 Minimization for Dictionary Learning

The idea that many important classes of signals can be well-represented by linear combinations of a small set of atoms selected from a given dictionary has had dramatic impact on the theory and practice of signal processing. For practical problems in which an appropriate sparsifying dictionary is not known ahead of time, a very popular and successful heuristic is to search for a dictionary that minimizes an appropriate sparsity surrogate over a given set of sample data. While this idea is appealing, the behavior of these algorithms is largely a mystery; although there is a body of empirical evidence suggesting they do learn very effective representations, there is little theory to guarantee when they will behave correctly, or when the learned dictionary can be expected to generalize. In this paper, we take a step towards such a theory. We show that under mild hypotheses, the dictionary learning problem is locally well-posed: the desired solution is indeed a local minimum of the $\ell^1$ norm. Namely, if $\mb A \in \Re^{m \times n}$ is an incoherent (and possibly overcomplete) dictionary, and the coefficients $\mb X \in \Re^{n \times p}$ follow a random sparse model, then with high probability $(\mb A,\mb X)$ is a local minimum of the $\ell^1$ norm over the manifold of factorizations $(\mb A',\mb X')$ satisfying $\mb A' \mb X' = \mb Y$, provided the number of samples $p = Ω(n^3 k)$. For overcomplete $\mb A$, this is the first result showing that the dictionary learning problem is locally solvable. Our analysis draws on tools developed for the problem of completing a low-rank matrix from a small subset of its entries, which allow us to overcome a number of technical obstacles; in particular, the absence of the restricted isometry property.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Sparsity and Robustness in Face Recognition

This report concerns the use of techniques for sparse signal representation and sparse error correction for automatic face recognition. Much of the recent interest in these techniques comes from the paper "Robust Face Recognition via Sparse Representation" by Wright et al. (2009), which showed how, under certain technical conditions, one could cast the face recognition problem as one of seeking a sparse representation of a given input face image in terms of a "dictionary" of training images and images of individual pixels. In this report, we have attempted to clarify some frequently encountered questions about this work and particularly, on the validity of using sparse representation techniques for face recognition.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dense Error Correction for Low-Rank Matrices via Principal Component Pursuit

We consider the problem of recovering a low-rank matrix when some of its entries, whose locations are not known a priori, are corrupted by errors of arbitrarily large magnitude. It has recently been shown that this problem can be solved efficiently and effectively by a convex program named Principal Component Pursuit (PCP), provided that the fraction of corrupted entries and the rank of the matrix are both sufficiently small. In this paper, we extend that result to show that the same convex program, with a slightly improved weighting parameter, exactly recovers the low-rank matrix even if "almost all" of its entries are arbitrarily corrupted, provided the signs of the errors are random. We corroborate our result with simulations on randomly generated matrices and errors.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Stable Principal Component Pursuit

In this paper, we study the problem of recovering a low-rank matrix (the principal components) from a high-dimensional data matrix despite both small entry-wise noise and gross sparse errors. Recently, it has been shown that a convex program, named Principal Component Pursuit (PCP), can recover the low-rank matrix when the data matrix is corrupted by gross sparse errors. We further prove that the solution to a related convex program (a relaxed PCP) gives an estimate of the low-rank matrix that is simultaneously stable to small entrywise noise and robust to gross sparse errors. More precisely, our result shows that the proposed convex program recovers the low-rank matrix even though a positive fraction of its entries are arbitrarily corrupted, with an error bound proportional to the noise level. We present simulation results to support our result and demonstrate that the new convex program accurately recovers the principal components (the low-rank matrix) under quite broad conditions. To our knowledge, this is the first result that shows the classical Principal Component Analysis (PCA), optimal for small i.i.d. noise, can be made robust to gross sparse errors; or the first that shows the newly proposed PCP can be made stable to small entry-wise perturbations.

0 citations0 reviewsNo code linkedOpen access