We consider the approximate sparse recovery problem in multi-hop Wireless Sensor Networks (WSNs) using Compressed Sensing/Compressive Sampling (CS). The goal is to recover the n-dimensional data ...values by querying only m ≪ n sensors based on some linear projection of sensor readings. To solve this problem, a distributed compressive sparse sampling (DCSS) algorithm is proposed based on sparse binary CS measurement matrix. Each sensor first samples the environment independently, then the fusion center (FC), acting as a pseudo-sensor, samples the sensor network to select a subset of sensors (m out of n) that respond to the FC through shortest path for data recovery purpose. The sparse binary matrix is designed using the unbalanced expander graph which achieves the state-of-the-art performance for CS schemes. This binary matrix can be interpreted as a sensor selection matrix whose fairness is analyzed. Extensive experiments on both synthetic and real data sets show that by querying only the minimum amount of m sensors using the DCSS algorithm, the CS recovery accuracy outperforms existing sparse random matrices and can be as good as those using random dense measurement matrices but using much less number of sensors. We also show that the sparse binary measurement matrix works well on compressible data which has the closest recovery result to the known best k-term approximation. The recovery is robust against noisy measurements and does not require regular WSN deployments (e.g., grids). The sparsity and binary properties of the measurement matrix contribute, to a great extent, the reduction of the in-network communication cost as well as the computational burden.
We introduce the first embedding of graphs of low bandwidth into ℓ1, with distortion depending only upon the bandwidth. We extend this result to a new graph parameter called tree-bandwidth, which is ...very similar to (but more restrictive than) treewidth. This represents the first constant distortion embedding of a non-planar class of graphs into ℓ1. Our results make use of a new technique that we call iterative embedding in which we define coordinates for a small number of points at a time.
Compressive Sensing (CS) shows that sparse signals can be exactly recovered from a limited number of random or deterministic projections when the measurement mode satisfies some specified conditions. ...Random matrices, with the drawbacks of large storage, low efficiency and high complexity, are hard to use in practical applications. Recent works explore expander graphs for efficient CS recovery, but there is no explicit construction of expanders. The widely used expanders are chosen at random based on the probabilistic method. In this paper, we propose a parameter based on the second-largest eigenvalue of the adjacency matrix to select optimized expanders from random expanders. The theoretical analysis and the numerical simulations both indicate the selection criteria proposed in this paper can pick up the high-performance expanders from the random expanders effectively.
Construction of halvers Manos, H.
Information processing letters,
03/1999, Volume:
69, Issue:
6
Journal Article
Peer reviewed
An ε-halver for
m elements is a comparator network, which splits the input list into two blocks, each of size
m
2
. The ε-halver has the property that if
S
k
is the set of the
k smallest elements in ...the input, where
k ⩽
m
2
, then at most
εk of the elements of
S
k
will fall in the right block. A similar statement holds for
L
k
, the set of the
k largest elements of the input, with respect to the left block. In this paper we introduce an explicit halver network with depth
D(ε) = A2
(log log(
1
ε
))
2
, where
A is some constant.
Compressive Sensing (CS) asserts that one can recover a sparse signal from a limited number of random or deterministic projections exactly if the measurement matrix satisfies the so-called RIP. ...People try to design deterministic matrices for CS because of the small storage, high efficiency and low complexity compared with the random matrices in practical applications. Recent works explore expander graphs for efficient CS reconstruction, but the existing expander graphs for CS are either difficult to obtain or restricted on the number of the vertices. In this paper, we propose an algorithm named zig-zag and replacement product expander graphs whose main idea is to produce another expander graph or an explicit family of expander graphs using two or more known expander graphs. Based on the proposed algorithm, the expander graphs are easy to obtain and the vertices of the graphs, corresponding to the length of the original signal and the measurement times, aren't restricted too much. Finally, numerical simulations are conducted to verify the better performance of the zig-zag product matrices compared with the random matrices.
Optimally Sequence Sparse Matching Pursuit Nguyen, Long; Ho, My
2010 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF),
2010-Nov.
Conference Proceeding
In this paper, we propose an improvement of Sparse Sequence Matching Pursuit algorithm, namely Optimally Sequence Sparse Matching Pursuit (OpSSMP), through experiments in two perspectives that ...includes to reduce the number of measurement and to omit K-sparse coefficient of signal. This is important to process various images which are different in number of sparse components so it plays an essential role when the algorithm maps to hardware. Although the running time of method is slower than SSMP, it remains comparable to state-of-the-art CoSaMP and SubSpace Pursuit algorithms.
This paper studies compressed sensing for the recovery of non-negative sparse vectors from a smaller number of measurements than the ambient dimension of the unknown vector. We construct sparse ...measurement matrices for the recovery of non-negative vectors, using perturbations of adjacency matrices of expander graphs with much smaller expansion coefficients than previously suggested schemes. These constructions are crucial in applications, such as DNA microarrays and sensor networks, where dense measurements are not practically feasible. We present a necessary and sufficient condition for lscr 1 optimization to successfully recover the unknown vector and obtain closed form expressions for the recovery threshold. We finally present a novel recovery algorithm that exploits expansion and is faster than lscr 1 optimization.
Mathematical Diseases Lipton, Richard J.
The P=NP Question and Gödel’s Lost Letter
Book Chapter
Underwood Dudley is a number theorist, who is perhaps best known for his popular books on mathematics. The most famous one is A Budget of Trisections, which studies the many failed attempts at the ...ancient problem of trisecting an angle with only a ruler and a compass 44. This problem is impossible, yet that has not stopped some people from working day and night looking for a solution. Trying to find such a solution is an obsession for some; it’s almost like they have a malady that forces them to work on the problem.
PDF
