# 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.

Hi could anyone discuss self serving bias?
what is self serving bias?
vishal
if you achieve something you are willing to take credit for that. If you don't achieve,you simply say it is because of external factors
Vamsi
I think simple and best example would be if we score good marks we say "I worked hard".If we don't get good marks we say "teacher didn't teach the lesson well".
Vamsi
is it universally applicable?
vishal
yes
Vamsi
kindly explain how
vishal
I have the same doubt... As we can search for meaning... But not able to understand the concept
SNEHAL
yes
Vamsi
atttibution is a social cognitive function that allows us to give, to attribute, feelings of thoughts to somebody that's not ourself. for example I can say that my friend is feeling sad today for some reasons because I can consider that my friend is different than me. does it help ?
Perle
Thank you Perle.Can I get another example?
Vamsi
imagine you are walking in the street and you see someone smiling. you can think "oh this person looks happy"
Perle
basically it's the ability to understand that others are not you and they can have their own feelings or thoughts
Perle
Thank you so much.
Vamsi
wait wait. my last example is wrong. seeing someone smiling and think they're happy is the theory of mind, not attribution
Perle
Okay
Suman
Is this definition correct "basically it's the ability to understand that others are not you and they can have their own feelings or thoughts."
Vamsi
yup ☺
Perle
but social cognitive functions are tricky. theory of mind and attribution are quite close !
Perle
Then can you please give me another example.
Vamsi
two examples : someone always talks during a class, while others listen to the professor. the intern attribution that you can think of is : this person doesn't like school
Perle
now this time, all students talk during a class. the external attribution that you can think of is : the class is boring
Perle
attribution is nothing but just the process by which we human explain our behaviour
Agnieszka
like when I get good marks..i will attribute this to my performance and study
Agnieszka
Hi Perle could you help me with one question
vishal
Is Self serving bias universal in attribution process?
vishal
self serving bias is like the tendency to perceive ourselves in very righteous manner
Agnieszka
it's more on focussing on the need to maintain high self esteem
Agnieszka
the basics are clear I needed to know more on the universal applicability about the SSB (self serving bias)
vishal
vishal yup thats a good idea ...
ecstasy
please what arw the two main ways of controlling behaviour?
patience and meditation
ChandraKumar
any one ,what is bio psychological model
EXTRA
Bio psychological model means bio means body and psychological means mind so bio psychological model is studies mind and body relationships
Nilamani
daily prayers and daily affirmations and daily excercise
Alban
and what is health belief model?
EXTRA
what us psychology
psychology is the study of mind. And also the study of human behavior.
Simisola
yeah
Oruta
thank you
Ndeh
Ok
Oruta
psychology is the systematic study of human and animal mind and its mental processes.
Christopher
psychology is the scientific study of the mind and behaviour...And it also includes the study of animals as well as humans.
kelson
Psychology is the scientific and systematic study of mental activities, behavior and cognitive process of organism to relationships between it's environment...
Nilamani
yes
Ahsan
What could be some short term and long terms goals one can have,in order to become an education psychologist?
hmmm
Maaruf
Short term: - contact a school psychologist and shadow them for a few days - study and keep up with college coursework - join psychology club/ groups Long term: - transfer to a 4 year university - choose wisely your graduate school - talk to graduates from those schools
Isela
thank you Isela Huerta :)
Hibba
how to recognize the person with psychological disorders?
Nawaz
Please keep in mind that it's not allowed to promote any social groups (whatsapp, facebook, etc...), exchange phone numbers, email addresses or ask for personal information on QuizOver's platform.
I want to start psychology courses, which one would you suggest i do first, and why? Im about to move to a different place.
open university
rauhahenki
it goes in chronological order, so to speak
rauhahenki
thank you
Amanda
how is Coursera is this matter, what's the best MOOC source?
Suvigya
Could you recommend any online course that would be useful for the purpose. Open university such as?
Swati
srikanth
Psychopharmacology
srikanth
Lot Of Courses.... in Which Side You Wanna Go In Particular?
srikanth
oh. well i wish to study before i go into college. counseling sounds good, people like to come to me for advise, and i am very detail oriented and love creative art stuff.
Amanda
@Swati have you tried Coursera
Suvigya
Child Counseling Abnormal Behaviors Addiction's - Rehabilitation Marriage Counseling and A lot More...
srikanth
Which University should I enroll for a Counseling Psychology.
Emmanuel
Yes, I've checked that. Are they good enough to start with? @suvigya
Swati
Yes, online university? Suggestions on that?
Swati
@srikanth i am in usa going to a different state/province. so online makes more sense. is it possible to be really good in more than one ☺
Amanda
yes i agree any suggestions for online university. or just where we can take courses/classes, partial university
Amanda
yah There is A lot of Certification Courses In ONLINE... And Distance Education..
srikanth
thank you for the responses
Amanda
can any 1 tell me how to how to joint indian army as Psychologist
Gaurav
can someone tell me which are some popular certification courses?
pavithra
For Psychologist
Gaurav
family Counselling. @Pavithra Nair..
srikanth
thanks
pavithra
hy
Jennifer
Any one knows where to find Free courses with certification in psychology?
Gian
It Depends On Place Where You Live In
srikanth
in Telangana Osmania University They Offered Different PG Diploma Courses They Collect Minimum Fee It's Too Low... 5k to 6k In Indian Currency
srikanth
Free online courses, without country bounds, do you know some?
Gian
what is motivation?
The good feeling of wanting to go forward; to a dream, wish or making yourself a better present or future.
Amanda
it could be intrinsic( as mentioned above) as well as extrinsic( salary etc. ) sometimes extrinsic motivation is detrimental to intrinsic..such that it takes away the enjoyment or zeal of doing that thing
Avish
it is the reason for a particular behavior or action.
Champro
hello Everyone..... I Need Some Information.... I've Completed Msc. Psychology In Hyderabad... How Can I Be A Approved Psychologist?
haha
Amit
hay Buddy... if You Can Help Me Let Me Know...
srikanth
Mahmoud
thank you Mahmoud Al..
srikanth
Motivation results in
progress to success
SK
peace I think I have bipolarity disorder I don't want to see a psychologist in this concern how can stop having swings in moods and depression?
try to meditate
Mahmoud
ruchi
why exactly should we meditate!!?
sanskar
you need a cognitive behavioral therapist, meditation will worsen
Suvigya
just 2 sessions changed my bipolar habits and saved my relationship with family and my partner, it is life saving
Suvigya
What does chronic mean?
Occurring over a period of time, at least 2 weeks or more
Wayne
chronic is human health condition/disease which decode diabetes,cancer etc.
SK
In thinking about the case of Candace described earlier, do you think that Candace benefitted or suffered as a result of consistently being passed on to the next grade?
what is a narcissist
Denise
isnt narcissist a chronic liar?
Steph
I believe newborns can
Steph
newborns starts to develop habits from 6-10 months after birth so sometimes they make bad traits
Poorvi
dominating personality
Deepak
are narcissists chronic liar?
Deepak
I feel like we learn things over Time and then apply these traits (whether bad or good) in our daily lives,but since new born are still very small they can't yet (unless they reach around the toddler phase)
Hibba
narcissistic person is a that type of person who loves himself only very much.....if somebody tells them anything they become very angry....
ChandraKumar
Yes, It's correct
SRINIVASULU
please which is the best school to study masters in psychology?
Anastasia
at 6-10 months you are no longer a newborn. newborns, however, only have traits consistent with survival and comfort. good and bad then, are perceptive consequences of the onlooker. a newborn will cry when hungry, sleep when tired or overwhelmed; these are traits of dependance not good or bad
narcissist are only chronic liars to themselves. they need to lie in order to feel in control/over and above any and everybody else.
what is psychology?
psychology is the study of mental processes and behaviour
Abdul
of human beings.
Abdul
psyche (mind)+ -ology (study of) hence means study of mind
Psyche also refers to soul. it is also used to be called study of soul. but this is old definition.
Abdul
it is method to help who needs help without any conditions, I think
Wounded
Got questions? Join the online conversation and get instant answers!