2009-10-22T20:21:49Z

The Geometry of Generalized Binary Search

This paper investigates the problem of determining a binary-valued function through a sequence of strategically selected queries. The focus is an algorithm called Generalized Binary Search (GBS), a well-known greedy approach to this problem. At each step, a query is selected that most evenly splits the hypotheses under consideration into two disjoint subsets, a natural generalization of the idea underlying classic binary search and Shannon-Fano coding. GBS is used in many applications including channel coding, experimental design, fault testing, machine diagnostics, disease diagnosis, job scheduling, image processing, computer vision, and machine learning. This paper develops novel incoherence and geometric conditions under which GBS achieves the information-theoretically optimal query complexity; i.e., given a collection of N hypotheses, GBS terminates with the correct function in O(log N) queries. Furthermore, a noise-tolerant version of GBS is developed that also achieves the optimal query complexity. These results are applied to learning multidimensional threshold functions, a problem arising routinely in image processing and machine learning.

2001-02-21T15:19:49Z

Thermalization of magnetically trapped metastable helium

We have observed thermalization by elastic collisions of magnetically trapped metastable helium atoms. Our method directly samples the reconstruction of a thermal energy distribution after the application of an RF knife. The relaxation time of our sample towards equilibrium gives an elastic collision rate constant close to the unitarity limit.

2010-02-03T21:13:39Z

High-Dimensional Matched Subspace Detection When Data are Missing

We consider the problem of deciding whether a highly incomplete signal lies within a given subspace. This problem, Matched Subspace Detection, is a classical, well-studied problem when the signal is completely observed. High- dimensional testing problems in which it may be prohibitive or impossible to obtain a complete observation motivate this work. The signal is represented as a vector in R^n, but we only observe m << n of its elements. We show that reliable detection is possible, under mild incoherence conditions, as long as m is slightly greater than the dimension of the subspace in question.

Laura Balzano

Bejamin Recht

Robert Nowak

2010-06-21T12:12:27Z

Online Identification and Tracking of Subspaces from Highly Incomplete Information

This work presents GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at each iteration, and each subspace update can be performed in linear time in the dimension of the subspace. The algorithm is derived by analyzing incremental gradient descent on the Grassmannian manifold of subspaces. With a slight modification, GROUSE can also be used as an online incremental algorithm for the matrix completion problem of imputing missing entries of a low-rank matrix. GROUSE performs exceptionally well in practice both in tracking subspaces and as an online algorithm for matrix completion.

Laura Balzano

Robert Nowak

Benjamin Recht

1994-10-06T01:01:54Z

Accretion Disc Turbulence and the X-Ray Power Spectra of Black Hole High States

The high state of black hole candidates is characterized by a quasi- thermal emission component at $kT \sim 1$ keV. In addition, this state tends to have very low variability which indicates that it is relatively stable, at least on {\it short} time scales. Most models of the high state imply that the bulk of the emission comes from an optically thick accretion disc; therefore, this state may be an excellent laboratory for testing our ideas about the physics of accretion discs. In this work we consider the implications of assuming that accretion disc viscosity arises from some form of turbulence. Specifically, we consider the simple case of three dimensional hydrodynamic turbulence. It is found that the coupling of such turbulence to acoustic modes in the disc can alter the disc emission. We calculate the amplitude and frequencies of this modulation, and we express our results in terms of the X-ray power spectral density. We compare our calculations with observations of the black hole candidate GS 1124-683, and show that for certain parameters we can reproduce some of the high frequency power. We then briefly explore mechanisms for producing the low frequency power, and note the difficulty that a single variability mechanism has in reproducing the full range of observed variability. In addition, we outline ways in which future spacecraft missions -- such as USA and XTE -- can further constrain our model, especially at frequencies above $\sim 10^2$ Hz.

Michael A. Nowak

Robert V. Wagoner

2010-02-28T18:23:11Z

Detecting Weak but Hierarchically-Structured Patterns in Networks

The ability to detect weak distributed activation patterns in networks is critical to several applications, such as identifying the onset of anomalous activity or incipient congestion in the Internet, or faint traces of a biochemical spread by a sensor network. This is a challenging problem since weak distributed patterns can be invisible in per node statistics as well as a global network-wide aggregate. Most prior work considers situations in which the activation/non-activation of each node is statistically independent, but this is unrealistic in many problems. In this paper, we consider structured patterns arising from statistical dependencies in the activation process. Our contributions are three-fold. First, we propose a sparsifying transform that succinctly represents structured activation patterns that conform to a hierarchical dependency graph. Second, we establish that the proposed transform facilitates detection of very weak activation patterns that cannot be detected with existing methods. Third, we show that the structure of the hierarchical dependency graph governing the activation process, and hence the network transform, can be learnt from very few (logarithmic in network size) independent snapshots of network activity.

Aarti Singh

Robert D. Nowak

Robert Calderbank

2008-02-04T18:40:30Z

Riesz transforms for the Dunkl harmonic oscillator

We define and investigate a system of Riesz transforms related to the Dunkl harmonic oscillator.

Adam Nowak

Krzysztof Stempak

2003-10-13T08:48:53Z

Domain wall mobility in nanowires: transverse versus vortex walls

The motion of domain walls in ferromagnetic, cylindrical nanowires is investigated numerically by solving the Landau-Lifshitz-Gilbert equation for a classical spin model in which energy contributions from exchange, crystalline anisotropy, dipole-dipole interaction, and a driving magnetic field are considered. Depending on the diameter, either transverse domain walls or vortex walls are found. The transverse domain wall is observed for diameters smaller than the exchange length of the given material. Here, the system behaves effectively one-dimensional and the domain wall mobility agrees with a result derived for a one-dimensional wall by Slonczewski. For low damping the domain wall mobility decreases with decreasing damping constant. With increasing diameter, a crossover to a vortex wall sets in which enhances the domain wall mobility drastically. For a vortex wall the domain wall mobility is described by the Walker-formula, with a domain wall width depending on the diameter of the wire. The main difference is the dependence on damping: for a vortex wall the domain wall mobility can be drastically increased for small values of the damping constant up to a factor of $1/\alpha^2$.

R. Wieser

U. Nowak

K. D. Usadel

2004-06-22T10:05:22Z

Multiscale likelihood analysis and complexity penalized estimation

We describe here a framework for a certain class of multiscale likelihood factorizations wherein, in analogy to a wavelet decomposition of an L^2 function, a given likelihood function has an alternative representation as a product of conditional densities reflecting information in both the data and the parameter vector localized in position and scale. The framework is developed as a set of sufficient conditions for the existence of such factorizations, formulated in analogy to those underlying a standard multiresolution analysis for wavelets, and hence can be viewed as a multiresolution analysis for likelihoods. We then consider the use of these factorizations in the task of nonparametric, complexity penalized likelihood estimation. We study the risk properties of certain thresholding and partitioning estimators, and demonstrate their adaptivity and near-optimality, in a minimax sense over a broad range of function spaces, based on squared Hellinger distance as a loss function. In particular, our results provide an illustration of how properties of classical wavelet-based estimators can be obtained in a single, unified framework that includes models for continuous, count and categorical data types.

Eric D. Kolaczyk

Robert D. Nowak

2010-01-29T20:09:54Z

Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation

Adaptive sampling results in dramatic improvements in the recovery of sparse signals in white Gaussian noise. A sequential adaptive sampling-and-refinement procedure called Distilled Sensing (DS) is proposed and analyzed. DS is a form of multi-stage experimental design and testing. Because of the adaptive nature of the data collection, DS can detect and localize far weaker signals than possible from non-adaptive measurements. In particular, reliable detection and localization (support estimation) using non-adaptive samples is possible only if the signal amplitudes grow logarithmically with the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the amplitude exceeds a constant, and localization is possible when the amplitude exceeds any arbitrarily slowly growing function of the dimension.

Jarvis Haupt

Rui Castro

Robert Nowak