Tuesday, March 14, 2017

Emmanuel Candès in Paris, Insense, Imaging M87, gauge and perspective duality, Structured signal recovery from quadratic measurements




Emmanuel Candès is in Paris for the week and will talk every day starting today. More information can be found here. Today we have four papers from different areas of compressive sensing. The first one has to do with sensor selection provided signals are sparse, the second is about imaging the structure of an unknown object usign sparse modeling, the third is about showing equivalency of  problem set-ups and finally, the last one is about nonlinear compressive sensing. Enjoy !




Sensor selection refers to the problem of intelligently selecting a small subset of a collection of available sensors to reduce the sensing cost while preserving signal acquisition performance. The majority of sensor selection algorithms find the subset of sensors that best recovers an arbitrary signal from a number of linear measurements that is larger than the dimension of the signal. In this paper, we develop a new sensor selection algorithm for sparse (or near sparse) signals that finds a subset of sensors that best recovers such signals from a number of measurements that is much smaller than the dimension of the signal. Existing sensor selection algorithms cannot be applied in such situations. Our proposed Incoherent Sensor Selection (Insense) algorithm minimizes a coherence-based cost function that is adapted from recent results in sparse recovery theory. Using six datasets, including two real-world datasets on microbial diagnostics and structural health monitoring, we demonstrate the superior performance of Insense for sparse-signal sensor selection.

An implementation of Insense is here: https://github.com/amirmohan/Insense





We propose a new imaging technique for radio and optical/infrared interferometry. The proposed technique reconstructs the image from the visibility amplitude and closure phase, which are standard data products of short-millimeter very long baseline interferometers such as the Event Horizon Telescope (EHT) and optical/infrared interferometers, by utilizing two regularization functions: the ℓ1-norm and total variation (TV) of the brightness distribution. In the proposed method, optimal regularization parameters, which represent the sparseness and effective spatial resolution of the image, are derived from data themselves using cross validation (CV). As an application of this technique, we present simulated observations of M87 with the EHT based on four physically motivated models. We confirm that ℓ1+TV regularization can achieve an optimal resolution of ∼20−30% of the diffraction limit λ/Dmax, which is the nominal spatial resolution of a radio interferometer. With the proposed technique, the EHT can robustly and reasonably achieve super-resolution sufficient to clearly resolve the black hole shadow. These results make it promising for the EHT to provide an unprecedented view of the event-horizon-scale structure in the vicinity of the super-massive black hole in M87 and also the Galactic center Sgr A*.



Common numerical methods for constrained convex optimization are predicated on efficiently computing nearest points to the feasible region. The presence of a design matrix in the constraints yields feasible regions with more complex geometries. When the functional components are gauges, there is an equivalent optimization problem---the gauge dual---where the matrix appears only in the objective function and the corresponding feasible region is easy to project onto. measurements. We revisit the foundations of gauge duality and show that the paradigm arises from an elementary perturbation perspective. We therefore put gauge duality and Fenchel duality on an equal footing, explain gauge dual variables as sensitivity measures, and show how to recover primal solutions from those of the gauge dual. In particular, we prove that optimal solutions of the Fenchel dual of the gauge dual are precisely the primal solutions rescaled by the optimal value. The gauge duality framework is extended beyond gauges to the setting when the functional components are general nonnegative convex functions, including problems with piecewise linear quadratic functions and constraints that arise from generalized linear models used in regression.


This paper concerns the problem of recovering an unknown but structured signal x∈Rn from m quadratic measurements of the form yr=|ar,x|2 for r=1,2,...,m. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (m much less than n). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove that projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any constraint set (convex or nonconvex) providing convergence guarantees to the global optimum even when the objective function and constraint set is nonconvex. Furthermore, these results hold with a number of measurements that is only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in recent literature. In a companion paper we demonstrate favorable properties for the optimization problem that may enable similar results to continue to hold more globally (over the entire ambient space). Collectively these two papers utilize and develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. The mathematical results in this paper also pave the way for a new generation of data-driven phase-less imaging systems that can utilize prior information to significantly reduce acquisition time and enhance image reconstruction, enabling nano-scale imaging at unprecedented speeds and resolutions.


Join the CompressiveSensing subreddit or the Google+ Community or the Facebook page and post there !

No comments:

Printfriendly