# 0.7 Compressed sensing  (Page 5/5)

 Page 5 / 5

Additionally, one may view the ${\ell }_{0}/{\ell }_{1}$ equivalence problem geometrically. In particular, given the measurements $y=\Phi x$ , we have an $\left(N-M\right)$ -dimensional hyperplane ${\mathcal{H}}_{y}=\left\{{x}^{\text{'}}\in {\mathbb{R}}^{N}:y=\Phi {x}^{\text{'}}\right\}=\mathcal{N}\left(\Phi \right)+x$ of feasible signals that could account for the measurements $y$ . Supposing the original signal $x$ is $K$ -sparse, the ${\ell }_{1}$ recovery program will recover the correct solution $x$ if and only if $\parallel {x}^{\text{'}}{\parallel }_{1}>{\parallel x\parallel }_{1}$ for every other signal ${x}^{\text{'}}\in {\mathcal{H}}_{y}$ on the hyperplane. This happens only if the hyperplane ${\mathcal{H}}_{y}$ (which passes through $x$ ) does not “cut into” the ${\ell }_{1}$ -ball of radius ${\parallel x\parallel }_{1}$ . This ${\ell }_{1}$ -ball is a polytope, on which $x$ belongs to a $\left(K-1\right)$ -dimensional “face.” If $\Phi$ is a random matrix with i.i.d. Gaussian entries, then the hyperplane ${\mathcal{H}}_{y}$ will have random orientation. To answer the question of how $M$ must relate to $K$ in order to ensure reliable recovery, it helps to observe that a randomlygenerated hyperplane $\mathcal{H}$ will have greater chance to slice into the ${\ell }_{1}$ ball as $\mathrm{dim}\left(\mathcal{H}\right)=N-M$ grows (or as $M$ shrinks) or as the dimension $K-1$ of the face on which $x$ lives grows. Such geometric arguments have been made precise by Donoho andTanner  [link] , [link] , [link] and used to establish a series of sharp bounds on CS recovery.

## Connections with dimensionality reduction

We have also identified  [link] a fundamental connection between the CS and the JL lemma. In order to make this connection,we considered the Restricted Isometry Property (RIP), which has been identified as a key property of the CS projectionoperator $\Phi$ to ensure stable signal recovery. We say $\Phi$ has RIP of order $K$ if for every $K$ -sparse signal $x$ ,

$\left(1-ϵ\right)\sqrt{\frac{M}{N}}\le \frac{{∥\Phi ,x∥}_{2}}{{∥x∥}_{2}}\le \left(1+ϵ\right)\sqrt{\frac{M}{N}}.$
A random $M×N$ matrix with i.i.d. Gaussian entries can be shown to have this property with high probability if $M=O\left(Klog\left(N/K\right)\right)$ .

While the JL lemma concerns pairwise distances within a finite cloud of points, the RIP concerns isometric embedding of an infinite number of points (comprising a union of $K$ -dimensional subspaces in ${\mathbb{R}}^{N}$ ). However, the RIP can in fact be derived by constructing an effective sampling of $K$ -sparse signals in ${\mathbb{R}}^{N}$ , using the JL lemma to ensure isometric embeddings for each of these points,and then arguing that the RIP must hold true for all $K$ -sparse signals. (See  [link] for the full details.)

## Stable embeddings of manifolds

Finally, we have also shown that the JL lemma can also lead to extensions of CS to other concise signal models. In particular, while conventional CS theory concerns sparse signal models, it is alsopossible to consider manifold-based signal models. Just as random projections can preserve the low- dimensional geometry (the union of hyperplanes) that corresponds to a sparse signal family, randomprojections can also guarantee a stable embedding of a low-dimensional signal manifold. We have the following result, which states that an RIP-like property holds for families of manifold-modeledsignals.

Theorem

Let $\mathcal{M}$ be a compact $K$ -dimensional Riemannian submanifold of ${\mathbb{R}}^{N}$ having condition number $\frac{1}{\tau }$ , volume $V$ , and geodesic covering regularity $R$ . Fix $0<ϵ<1\text{and}0<\rho <1$ . Let Φ be a random M × N orthoprojector with

$M=O\left(\frac{K\text{log}\left(NVR{\tau }^{-1}{ϵ}^{-1}\right)\text{log}\left(\frac{1}{\rho }\right)}{{ϵ}^{2}}\right)$
If $M\le N$ , then with probability at least $1-\rho$ the following statement holds: For every pair of points ${x}_{1}$ , ${x}_{2}\in \mathcal{M}$ ,
$\left(1-ϵ\right)\sqrt{\frac{M}{N}}\le \frac{{∥\Phi ,{x}_{1},-,\Phi ,{x}_{2}∥}_{2}}{{∥{x}_{1},-,{x}_{2}∥}_{2}}\le \left(1+ϵ\right)\sqrt{\frac{M}{N}}$

The proof of this theorem appears in [link] and again involves the JL lemma. Due to the limited complexity of a manifold model, it is possible to adequately characterize the geometry using asufficiently fine sampling of points drawn from the manifold and its tangent spaces. In essence, manifolds with higher volume or with greater curvature have more complexity and require a moredense covering for application of the JL lemma; this leads to an increased number of measurements. The theorem also indicates that the requisite number of measurements depends on the geodesic covering regularity of the manifold, a minor technical concept which is also discussed in [link] .

This theorem establishes that, like the class of $K$ -sparse signals, a collection of signals described by a $K$ -dimensional manifold $\mathcal{M}\subset {\mathbb{R}}^{N}$ can have a stable embedding in an $M$ -dimensional measurement space. Moreover, the requisite number of random measurements $M$ is once again linearly proportional to the information level (or number of degrees of freedom) $K$ in the concise model. This has a number of possible implications for manifold-based signal processing. Manifold-modeledsignals can be recovered from compressive measurements (using a customized recovery algorithm adapted to the manifold model, in contrast with sparsity-based recovery algorithms) [link] , [link] ; unknown parameters in parametric models can be estimated from compressive measurements; multi-class estimation/classification problems can be addressed [link] by considering multiple manifold models; and manifold learning algorithms may be efficiently executed by applying them simply to the projection of a manifold-modeled data set to a low-dimensional measurement space [link] . (As an example, [link] (d) shows the result of applying the ISOMAP algorithm on a random projection of a data set from ${\mathbb{R}}^{4096}$ down to ${\mathbb{R}}^{15}$ ; the underlying parameterization of the manifold is extracted with little sacrifice in accuracy.) In all of this it isnot necessary to adapt the sensing protocol to the model; the only change from sparsity-based CS would be the methods for processing or decoding the measurements. In the future, more sophisticated concise models will likely lead to further improvements in signal understanding from compressive measurements.

what does nano mean?
nano basically means 10^(-9). nanometer is a unit to measure length.
Bharti
do you think it's worthwhile in the long term to study the effects and possibilities of nanotechnology on viral treatment?
absolutely yes
Daniel
how to know photocatalytic properties of tio2 nanoparticles...what to do now
it is a goid question and i want to know the answer as well
Maciej
Abigail
for teaching engĺish at school how nano technology help us
Anassong
Do somebody tell me a best nano engineering book for beginners?
what is fullerene does it is used to make bukky balls
are you nano engineer ?
s.
fullerene is a bucky ball aka Carbon 60 molecule. It was name by the architect Fuller. He design the geodesic dome. it resembles a soccer ball.
Tarell
what is the actual application of fullerenes nowadays?
Damian
That is a great question Damian. best way to answer that question is to Google it. there are hundreds of applications for buck minister fullerenes, from medical to aerospace. you can also find plenty of research papers that will give you great detail on the potential applications of fullerenes.
Tarell
what is the Synthesis, properties,and applications of carbon nano chemistry
Mostly, they use nano carbon for electronics and for materials to be strengthened.
Virgil
is Bucky paper clear?
CYNTHIA
so some one know about replacing silicon atom with phosphorous in semiconductors device?
Yeah, it is a pain to say the least. You basically have to heat the substarte up to around 1000 degrees celcius then pass phosphene gas over top of it, which is explosive and toxic by the way, under very low pressure.
Harper
Do you know which machine is used to that process?
s.
how to fabricate graphene ink ?
for screen printed electrodes ?
SUYASH
What is lattice structure?
of graphene you mean?
Ebrahim
or in general
Ebrahim
in general
s.
Graphene has a hexagonal structure
tahir
On having this app for quite a bit time, Haven't realised there's a chat room in it.
Cied
what is biological synthesis of nanoparticles
what's the easiest and fastest way to the synthesize AgNP?
China
Cied
types of nano material
I start with an easy one. carbon nanotubes woven into a long filament like a string
Porter
many many of nanotubes
Porter
what is the k.e before it land
Yasmin
what is the function of carbon nanotubes?
Cesar
I'm interested in nanotube
Uday
what is nanomaterials​ and their applications of sensors.
what is nano technology
what is system testing?
preparation of nanomaterial
how did you get the value of 2000N.What calculations are needed to arrive at it
Privacy Information Security Software Version 1.1a
Good
Berger describes sociologists as concerned with
Got questions? Join the online conversation and get instant answers!