23 January 2014
Title: Efficient data collection in participatory sensing
Participatory sensing is becoming a more and more important means of sharing sensory information. However, for taking each measurement, the participating devices have to consume certain amounts of resources, e.g., battery energy, privacy, and network bandwidth. To efficiently utilize these resources, we propose a scheme which allows nearby devices to collaborate. A 2-step algorithm is proposed to adaptively choose the device for actively sensing. When the moving trajectories of participating devices are periodic or are randomly generated by markov chains, we prove the asymptotical optimality of the proposed algorithm. We simulate our proposed scheme in two scenarios : sensors boxes are equipped on: i) the bus system in Lausanne and ii)taxis in San Francisco. Results have shown that the proposed scheme maintains the sensing coverage, is energy efficient and is fair to all participants.
Posted by Runwei Zhang at 13:16
Posted by Runwei Zhang at 13:16
Here is the abstract:
Capture Light Field with Plenoptic camera
The very first light fields were captured by Lippmann in 1908. It took over 100 years to bring Plenoptic cameras to the market.
In this TAM, I will talk about how does Plenoptic camera capture the light field and the difference between camera array. The acquisition of light field is quite difficult since it is a band-unlimited signal unless scene is totally flat painted with band-limited texture. I will try to build a model to analyze the imaging process. More specifically, I will look into the trade-offs inside a Plenoptic camera, such as focal length, size of the micro-lens array, pixel size, etc. And how to use these factors improve our acquisition strategies.
Based on these analysis, I will also discuss the possibility to do light field super-resolution, stitching and rendering.
Posted by Runwei Zhang at 13:14
Recursive Compressive Sampling
We propose a method for performing compressed sensing (CS) on streaming data. The method comprises sequentially processing the input stream through overlapping windowing via:
a) recursive sampling, in which previously observed portion of the stream is leveraged in obtaining new samples, and
b) recursive estimation, in which previously obtained estimates are used for warm-start in iterative LASSO solvers.
We study the computational complexity of the proposed scheme as a function of the window size as well as the sliding step. Furthermore, we highlight the benefit of sampling redundant information in reducing the estimation error variance, and propose using voting strategies for further ameliorating the robustness of the estimation procedure.
Our simulation studies illustrate substantive speedup and improved estimation accuracy over a "naive approach."
(This is joint work with O. Ocal)
Keywords: Compressed Sensing, recursive estimation, iterative optimization, LASSO
Posted by Runwei Zhang at 13:14
I'll talk about what I learned in the Fukushima session at the European Geosciences Union assembly last week in Vienna: a wider perspective of the problem, who is working on it, what they are doing, and new ideas to improve our last algorithm.
Posted by Runwei Zhang at 13:13
Sampling high-dimensional bandlimited fields on low-dimensional manifolds.
Consider the problem of sampling a bandlimited spatial field using mobile sensors. Classical sampling theory commonly uses the spatial density of samples as the performance metric of a sampling scheme. We argue that in the mobile sensing paradigm, a more relevant metric is the path density, or total distance traveled by the sensors per unit spatial volume. We introduce the problem of designing sampling trajectories with minimal path density subject to the constraint that bandlimited spatial fields can be perfectly reconstructed using samples taken on these trajectories. We obtain partial solutions to this problem from certain restricted classes of trajectories. Our results for trajectories can be generalized to results for higher dimensional sampling manifolds. Our results have applications in environment monitoring with mobile sensors, and also in designing scanning schemes for Magnetic Resonance Imaging (MRI).
Posted by Runwei Zhang at 13:13
In this talk, I will consider the group of signals which can be (precisely) reconstructed from a finite number of samples. More specifically, I talk about the class of signals with sparse representation in a known domain and signals with finite rate of innovations (FRI). The recently introduced framework of infinite-dimensional compressed seining shows that the signals in the former class can be recovered from a finite number of random samples in a different domain. The recovery algorithm solves a basis pursuit problem after a proper selection of the range and the number of random samples. On the other hand, in the latter class, a limited group of FRI signals can be reconstructed from carefully-chosen samples using the annihilating filter method. This method is very sensitive to noise and cannot be easily generalized to all of the signals in this class. Motivated by the infinite-dimensional compressed sensing, I am trying to find a new recovery algorithm for FRI signals by solving a basis pursuit problem. The new algorithm (if it succeeds) will be more robust to the noise and can be extended to all of the signals in this class.
Posted by Runwei Zhang at 13:12
Relighting and Subsurface Light Transport
Image formation is a sophisticated process involving a complex interplay of angular and spatial dimensions of incident illumination and is completely determined by the scene's apparent Bidirectional Scattering Distribution Function (BSDF). Due to the high dimensionality of BSDF, inverse rendering is severely ill posed in most cases. We take a fresh look at the Light Transport Matrix (LTM) that models spatial interactions of light with the scene and provide two new array of array representations for the LTM, inspired from light field imaging. The first representation allows us to isolate the elusive subsurface scattering component of the BSDF, from a few observations of the object under spatially varying illumination patterns. Connected component analysis on the second representation lets us to learn a material specific dictionary of subsurface light transport functions which can act as a strong prior on subsurface light transport during inverse rendering under arbitrary, uncontrollable, real-world illuminations. Finally, we will present the proposed forward model that incorporates the learnt prior.
Posted by Runwei Zhang at 13:11
Imagine that you are blindfolded inside an unknown room. You snap your fingers and listen to the room’s response. Can you hear the shape of the room? Some people can do it naturally, but can we design computer algorithms that hear rooms? We show how to compute the shape of a convex polyhedral room from its response to a known sound, recorded by a few microphones. Geometric relationships between the arrival times of echoes enable us to “blindfoldedly” estimate the room geometry. We achieve this by exploiting the properties of Euclidean distance matrices. Furthermore, we show that under mild conditions, first-order echoes provide a unique description of convex polyhedral rooms. Our algorithm starts from the recorded impulse responses and proceeds by learning the correct assignment of echoes to walls. The geometry of the microphone array is arbitrary, as well as the loudspeaker location: As long as the microphones can hear the echoes, we can position them as we want. In contrast to earlier methods, our proposed algorithm reconstructs the full three-dimensional geometry of the room from a single sound emission. Besides answering a basic question about the inverse problem of room acoustics, our results find applications in areas such as architectural acoustics, indoor localization, virtual reality and audio forensics.
Posted by Runwei Zhang at 13:10
Randomized Kaczmarz algorithm
We propose and analyze a randomized iterative variant of the popular Kaczmarz algorithm for solving large-scale linear systems. The scheme features exponential convergence in the m.s to the minimum-norm least-squares solution of a given linear system of equations. The expected number of arithmetic operations is proportional to the squared condition number of the system multiplied by the number of non-zero entries of the input matrix. We experimentally test the performance against the vastly mature literature of state-of-art linear solvers and showcase improvements.
In sensor networks, we study the problem of estimation from noisy relative measurements, i.e., differences of nodal values across edges. We use Randomized Kaczmarz to design and analyze a new class of distributed asynchronous consensus algorithms, and analyze the convergence rate depending solely on properties of the network topology. Inspired by the analytical insights, we propose Randomized Kaczmarz Over-smoothing (RKO), which has demonstrated, in both theory and simulations, improvement over existing protocols in terms of both convergence speed-up and energy savings.
(This is joint work with A. Zouzias)
Keywords: Randomized algorithms, Least Squares Estimation, Distributed algorithms, Consensus, Wireless Sensor Networks.
Posted by Runwei Zhang at 13:08
|Page : 1 2 Next » |