K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance by Piotr Indyk, Eric Price. The abstract reads:
We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m = O(k log(n/k)) and a 1 + epsilon approximation factor, which matches the best achievable bound for other error measures, such as the L_1 norm. Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems.
Fast global convergence of gradient methods for high-dimensional statistical recovery by Alekh Agarwal, Sahand N. Negahban, Martin J. Wainwright. The abstract reads:
Many statistical M-estimators are based on convex optimization problems formed by the combination of a data-dependent loss function with a norm-based regularizer. We analyze the convergence rates of projected gradient methods for solving such problems, working within a high-dimensional framework that allows the data dimension d to grow with (and possibly exceed) the sample size n. This high-dimensional structure precludes the usual global assumptions---namely, strong convexity and smoothness conditions---that underlie much of classical optimization analysis. We define appropriately restricted versions of these conditions, and show that they are satisfied with high probability for various statistical models. Under these conditions, our theory guarantees that projected gradient descent has a globally geometric rate of convergence up to the \emph{statistical precision} of the model, meaning the typical distance between the true unknown parameter $\theta^*$ and an optimal solution $\hat{\theta}$. This result is substantially sharper than previous convergence results, which yielded sublinear convergence, or linear convergence only up to the noise level. Our analysis applies to a wide range of $M$-estimators and statistical models, including sparse linear regression using Lasso ($\ell_1$-regularized regression); group Lasso for block sparsity; log-linear models with regularization; low-rank matrix recovery using nuclear norm regularization; and matrix decomposition. Overall, our analysis reveals interesting connections between statistical precision and computational efficiency in high-dimensional estimation.
Compressive Network Analysis by Xiaoye Jiang, Yuan Yao, Han Liu, Leonidas Guibas. The abstract reads:
Modern data acquisition routinely produces massive amounts of network data. Though many methods and models have been proposed to analyze such data, the research of network data is largely disconnected with the classical theory of statistical learning and signal processing. In this paper, we present a new framework for modeling network data, which connects two seemingly different areas: network data analysis and compressed sensing. From a nonparametric perspective, we model an observed network using a large dictionary. In particular, we consider the network clique detection problem and show connections between our formulation with a new algebraic tool, namely Randon basis pursuit in homogeneous spaces. Such a connection allows us to identify rigorous recovery conditions for clique detection problems. Though this paper is mainly conceptual, we also develop practical approximation algorithms for solving empirical problems and demonstrate their usefulness on real-world datasets.
Accelerated Noncontrast-Enhanced Pulmonary Vein MRA With Distributed Compressed Sensing by Mehmet Akcakaya, Peng Hu, Michael L. Chuang, Thomas H. Hauser, Long H. Ngo, Warren J. Manning, Vahid Tarokh, and Reza Nezafat. The introduction reads:
Purpose: To investigate the efficacy of distributed compressed sensing (CS) to accelerate free-breathing, electrocardiogram (ECG)-triggered noncontrast pulmonary vein (PV) magnetic resonance angiography (MRA).
Weighted l_p Constraints in Noisy Compressed Sensing by Laurent Jacques, David Kenrik Hammond and Jalal Fadili.
Primal-Dual TV Reconstruction in Refractive Deflectometry by Adriana Gonzalez, Laurent Jacques, Emmanuel Foumouo and Philippe Antoine. The inroduction reads:
Refractive deflectometry is a tomographic modality that measure light ray deflection when passing through transparent objects [1]. Combining multiple parallel light rays under various incident angles allows one to image the internal refractive-index distribution (or map) of complex materials (like optical fibers) while escaping from some limitations of interferometric systems (e.g., unstability to object vibrations, thickness measurement range).
* General Constructions of Sampling Matrices for Compressed SensingApril 15, 2011, 12-1 PMCredit photo: ESA/NASA, Einstein Rings
Arya Mazumdar
Affiliation: University of Maryland
* Underwater Sensor Networks: Random Access and Compressive SensingProfessor Milica Stojanovic
Northeastern University
DateTime:
Wednesday, April 27, 2011 - 10:00 - 12:00
No comments:
Post a Comment