<< Chapter < Page Chapter >> Page >
This module introduces the spark and the null space property, two common conditions related to the null space of a measurement matrix that ensure the success of sparse recovery algorithms. Furthermore, the null space property is shown to be a necessary condition for instance optimal or uniform recovery guarantees.

A natural place to begin in establishing conditions on Φ in the context of designing a sensing matrix is by considering the null space of Φ , denoted

N ( Φ ) = { z : Φ z = 0 } .

If we wish to be able to recover all sparse signals x from the measurements Φ x , then it is immediately clear that for any pair of distinct vectors x , x ' Σ K = x : x 0 K , we must have Φ x Φ x ' , since otherwise it would be impossible to distinguish x from x ' based solely on the measurements y . More formally, by observing that if Φ x = Φ x ' then Φ ( x - x ' ) = 0 with x - x ' Σ 2 K , we see that Φ uniquely represents all x Σ K if and only if N ( Φ ) contains no vectors in Σ 2 K . There are many equivalent ways of characterizing this property; one of the most common is known as the spark   [link] .

The spark

The spark of a given matrix Φ is the smallest number of columns of Φ that are linearly dependent.

This definition allows us to pose the following straightforward guarantee.

(corollary 1 of [link] )

For any vector y R M , there exists at most one signal x Σ K such that y = Φ x if and only if spark ( Φ ) > 2 K .

We first assume that, for any y R M , there exists at most one signal x Σ K such that y = Φ x . Now suppose for the sake of a contradiction that spark ( Φ ) 2 K . This means that there exists some set of at most 2 K columns that are linearly dependent, which in turn implies that there exists an h N ( Φ ) such that h Σ 2 K . In this case, since h Σ 2 K we can write h = x - x ' , where x , x ' Σ K . Thus, since h N ( Φ ) we have that Φ ( x - x ' ) = 0 and hence Φ x = Φ x ' . But this contradicts our assumption that there exists at most one signal x Σ K such that y = Φ x . Therefore, we must have that spark ( Φ ) > 2 K .

Now suppose that spark ( Φ ) > 2 K . Assume that for some y there exist x , x ' Σ K such that y = Φ x = Φ x ' . We therefore have that Φ ( x - x ' ) = 0 . Letting h = x - x ' , we can write this as Φ h = 0 . Since spark ( Φ ) > 2 K , all sets of up to 2 K columns of Φ are linearly independent, and therefore h = 0 . This in turn implies x = x ' , proving the theorem.

It is easy to see that spark ( Φ ) [ 2 , M + 1 ] . Therefore, [link] yields the requirement M 2 K .

The null space property

When dealing with exactly sparse vectors, the spark provides a complete characterization of when sparse recovery is possible. However, when dealing with approximately sparse signals we must introduce somewhat more restrictive conditions on the null space of Φ   [link] . Roughly speaking, we must also ensure that N ( Φ ) does not contain any vectors that are too compressible in addition to vectors that are sparse. In order to state the formal definition we define the following notation that will prove to be useful throughout much of this course . Suppose that Λ { 1 , 2 , , N } is a subset of indices and let Λ c = { 1 , 2 , , N } Λ . By x Λ we typically mean the length N vector obtained by setting the entries of x indexed by Λ c to zero. Similarly, by Φ Λ we typically mean the M × N matrix obtained by setting the columns of Φ indexed by Λ c to zero. We note that this notation will occasionally be abused to refer to the length | Λ | vector obtained by keeping only the entries corresponding to Λ or the M × | Λ | matrix obtained by only keeping the columns corresponding to Λ . The usage should be clear from the context, but typically there is no substantive difference between the two.

A matrix Φ satisfies the null space property (NSP) of order K if there exists a constant C > 0 such that,

h Λ 2 C h Λ c 1 K

holds for all h N ( Φ ) and for all Λ such that | Λ | K .

The NSP quantifies the notion that vectors in the null space of Φ should not be too concentrated on a small subset of indices. For example, if a vector h is exactly K -sparse, then there exists a Λ such that h Λ c 1 = 0 and hence [link] implies that h Λ = 0 as well. Thus, if a matrix Φ satisfies the NSP then the only K -sparse vector in N ( Φ ) is h = 0 .

To fully illustrate the implications of the NSP in the context of sparse recovery, we now briefly discuss how we will measure the performance of sparse recovery algorithms when dealing with general non-sparse x . Towards this end, let Δ : R M R N represent our specific recovery method. We will focus primarily on guarantees of the form

Δ ( Φ x ) - x 2 C σ K ( x ) 1 K

for all x , where we recall that

σ K ( x ) p = min x ^ Σ K x - x ^ p .

This guarantees exact recovery of all possible K -sparse signals, but also ensures a degree of robustness to non-sparse signals that directly depends on how well the signals are approximated by K -sparse vectors. Such guarantees are called instance-optimal since they guarantee optimal performance for each instance of x   [link] . This distinguishes them from guarantees that only hold for some subset of possible signals, such as sparse or compressible signals — the quality of the guarantee adapts to the particular choice of x . These are also commonly referred to as uniform guarantees since they hold uniformly for all x .

Our choice of norms in  [link] is somewhat arbitrary. We could easily measure the reconstruction error using other p norms. The choice of p , however, will limit what kinds of guarantees are possible, and will also potentially lead to alternative formulations of the NSP. See, for instance,  [link] . Moreover, the form of the right-hand-side of [link] might seem somewhat unusual in that we measure the approximation error as σ K ( x ) 1 / K rather than simply something like σ K ( x ) 2 . However, we will see later in this course that such a guarantee is actually not possible without taking a prohibitively large number of measurements, and that [link] represents the best possible guarantee we can hope to obtain (see "Instance-optimal guarantees revisited" ).

Later in this course, we will show that the NSP of order 2 K is sufficient to establish a guarantee of the form [link] for a practical recovery algorithm (see "Noise-free signal recovery" ). Moreover, the following adaptation of a theorem in  [link] demonstrates that if there exists any recovery algorithm satisfying [link] , then Φ must necessarily satisfy the NSP of order 2 K .

(theorem 3.2 of [link] )

Let Φ : R N R M denote a sensing matrix and Δ : R M R N denote an arbitrary recovery algorithm. If the pair ( Φ , Δ ) satisfies [link] then Φ satisfies the NSP of order 2 K .

Suppose h N ( Φ ) and let Λ be the indices corresponding to the 2 K largest entries of h . We next split Λ into Λ 0 and Λ 1 , where | Λ 0 | = | Λ 1 | = K . Set x = h Λ 1 + h Λ c and x ' = - h Λ 0 , so that h = x - x ' . Since by construction x ' Σ K , we can apply [link] to obtain x ' = Δ ( Φ x ' ) . Moreover, since h N ( Φ ) , we have

Φ h = Φ x - x ' = 0

so that Φ x ' = Φ x . Thus, x ' = Δ ( Φ x ) . Finally, we have that

h Λ 2 h 2 = x - x ' 2 = x - Δ ( Φ x ) 2 C σ K ( x ) 1 K = 2 C h Λ c 1 2 K ,

where the last inequality follows from [link] .

Questions & Answers

what's a psy.d degree
Robin Reply
Psychology Doctorate. The main difference between PsyD and PhD Psychology is that PsyD mainly focuses on clinical sessions and PhD focuses on research.
so most of the phd holders become professors teaching what they have learnt
Hi, I have a question. What factors influence social facilitation and social inhibition in groups?
Amritpal Reply
it really depends on that person on how the can task in life either they can work better with other people or you do worse working with people.
the task
they task
Do you know of any studies done to show social facilitation and social inhibition
social facilitation is often influenced by the person's perception of the situation and their appraisal of the task. for example, a track athlete who views their competition as a challenge rather than a threat, will tend to run the fastest they have ever ran under a large crowd.
Another condition is if the person has mastered the ability to perform that task. A track athlete who trains everyday, will perform above average under a large crowd, however, someone who does not run, will tend to do worse than their actual ability under a large crowd
social inhibition can be explained through evolutionary biology or attachment personality theory. some people develop an avoidance personality trait, which when they feel under pressure, they tend to leave the group or avoid a gathering due to high lev of stress
Does anyone know how I can transfer my higher national diploma credits in usa?
Qwanta Reply
Oh wow. I never realised there was a chat on this app!
Amritpal Reply
Then welcome dearest
Thank you! ❤️
thank you
Hello Ana, good afternoon from here
Philip Reply
hello im new student here.
Junalyn Reply
o sorry madm
I m also student.
what is easier option to psychology?
I'm new too
As in the the specialisation or ?
good morning
understanding human nature is what we are going to talk about.
okay, go ahead
“ Every child is left to evaluate his experiences for himself, and to take care of his own personal development outside the classroom. There is no tradition for the acquisition of a true knowledge of the human psyche. The science of human nature thus finds itself today in the position that chemis
well, I think every individual is different and to a great extent we can't say confidently that we understand the human nature in its entirety
lack determines what we will become in life?.
Not 100% but it plays a huge role
Hi! I wasn't aware there was a chat feature on this app 😊
👍Philip Anyaegbu
yes Ana I'm here
alternatively we are different, we have basic similar qualities
Yes true Bridget.
hello there
who we are how we think what we do insight
@ bridget. yes that's true
Ana ioanidis? do you speak Greek?
Qwanta no I dont speak Greek my husband does
are you a psychologist? or your husband?
I need some reliable informations about my studies...
not a psychologist
I ask questions
so what is the cause why a person experiences a psychological disorder if it not of their own?
Junalyn Reply
it's partly genetics,culture, environment and substance abuse. generally these are the common factors which can lead to most of the disorders
r u proficcer
u r psychology subject
not a professor but a clinical psychologist
can i ask you, i keep getting headache, and had a history of hypothyroid ans diagnosed as having mild anxiety disorder. i want to finish. my undergraduate psychology thesis.. but always unable to have good ambition and energy to focus on writing the case and the theories... whats the best remedy
had a headache and have a history
297 according to the DSM 5
how many disorders are there
Janareon Reply
interesting question
it is😅
I'm guessing it's in the tens of thousands, maybe hundreds if you include counter interactions and stuff like it. although I'm sure it's almost impossible to know for sure, unless you're very rich and connected to the right people. but as I said: guessing.
There are more than 200 classified forms of mental illness. Some of the more common disorders are: clinical depression, bipolar disorder, dementia, schizophrenia and anxiety disorders. Symptoms may include changes in mood, personality, personal habits and/or social withdrawal. that is what I think
too difficult to number. diagnosing a disorder is just checking off boxes on a compilation of symptoms that might match any particular condition on the DSM
what is psychology of the guest
Lirilong Reply
I don't understand the question can you elaborate?
the study of philosophy gives to the sociologist
Aman Reply
why women are viewed as far more emotional than men?
Wario Reply
because they actually are ,I guess.
May be they are biologically milder than man. It does not mean they are not equal with man. Man can also be emotional and can are oppressed with traditional norms. For example, man are not to be cry, in actual man are also emotional being and they cannot have the right to show their sentiment.
sollungal bro sollungal...
because of she has hormonal fluctuations than men..
usually women are more emotional than men and they are multi talented people
Both men and women are capable of expressing emotions. But women has the highest percentage of doing that. Because our society is conditioned by nature in such a way that men are expected to suppress their emotions and motivate them through their acts or thoughts, which has it's side effects of....
denial of any emotion which they feel that useless at that point. Women in the other hand were encouraged/not controlled to suppress their emotions and let them out what they feel about it. I feel that's the wonderful superpower of the women.
Men's emotion comes mostly with memories triggered by senses. That means, they thoughts have the power to decide whether to let go of emotions or not.
because women tend to be more agreeable than men.
women at a young age are conditioned to be more in tune with emotion than man should be less
The question is "Why women Viewed are as far more emotional than men ?" it's not a question whether women are more emotional than men. This is more an issue about the point of view from the observer, his/her assumption what emotional behavior is or what emotional behavior is.
The anwers are answers more to the question " Are women more emotional than men?"
hi are you on what'sap
Wunuji Reply
no not really a fan of social laziness
is there any way for a Btech E.C.E. graduate to take on MSC. PSYCHOLOGY
ya you can just by cracking entrance , if in India
Any stream in UG can go for M.Sc (Psychology)
classification of traits and how they are measured
chinedu Reply
what was Freud's first name?
Robin Reply
Sigismund Schlomo Freud
Sigmund Freud
Leon Vygotsky and Sergei Rubenstein please tell me contributions of these personalities in in 4 lines
sigmund Freud
Lev Vygotsky was the founder of socio-cultural theory
So psychology was based off of the Greek gods I that right or no?
Tanya Reply
psychology is the study. anything -ology is the study of a certain field. Psyche is a mortal woman who becomes divine in Greek mythology. The etymology of the word "psyche" in Greek means "spirit" or "soul"
Got questions? Join the online conversation and get instant answers!
Jobilize.com Reply

Get the best Algebra and trigonometry course in your pocket!

Source:  OpenStax, An introduction to compressive sensing. OpenStax CNX. Apr 02, 2011 Download for free at http://legacy.cnx.org/content/col11133/1.5
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'An introduction to compressive sensing' conversation and receive update notifications?