# 3.1 Null space conditions

 Page 1 / 1
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 $\Phi$ in the context of designing a sensing matrix is by considering the null space of $\Phi$ , denoted

$\mathcal{N}\left(\Phi \right)=\left\{z:\Phi z=0\right\}.$

If we wish to be able to recover all sparse signals $x$ from the measurements $\Phi x$ , then it is immediately clear that for any pair of distinct vectors $x,{x}^{\text{'}}\in {\Sigma }_{K}=\left\{x,:,{∥x∥}_{0},\le ,K\right\}$ , we must have $\Phi x\ne \Phi {x}^{\text{'}}$ , since otherwise it would be impossible to distinguish $x$ from ${x}^{\text{'}}$ based solely on the measurements $y$ . More formally, by observing that if $\Phi x=\Phi {x}^{\text{'}}$ then $\Phi \left(x-{x}^{\text{'}}\right)=0$ with $x-{x}^{\text{'}}\in {\Sigma }_{2K}$ , we see that $\Phi$ uniquely represents all $x\in {\Sigma }_{K}$ if and only if $\mathcal{N}\left(\Phi \right)$ contains no vectors in ${\Sigma }_{2K}$ . 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 $\Phi$ is the smallest number of columns of $\Phi$ that are linearly dependent.

This definition allows us to pose the following straightforward guarantee.

## (corollary 1 of [link] )

For any vector $y\in {\mathbb{R}}^{M}$ , there exists at most one signal $x\in {\Sigma }_{K}$ such that $y=\Phi x$ if and only if $\mathrm{spark}\left(\Phi \right)>2K$ .

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

Now suppose that $\mathrm{spark}\left(\Phi \right)>2K$ . Assume that for some $y$ there exist $x,{x}^{\text{'}}\in {\Sigma }_{K}$ such that $y=\Phi x=\Phi {x}^{\text{'}}$ . We therefore have that $\Phi \left(x-{x}^{\text{'}}\right)=0$ . Letting $h=x-{x}^{\text{'}}$ , we can write this as $\Phi h=0$ . Since $\mathrm{spark}\left(\Phi \right)>2K$ , all sets of up to $2K$ columns of $\Phi$ are linearly independent, and therefore $h=0$ . This in turn implies $x={x}^{\text{'}}$ , proving the theorem.

It is easy to see that $\mathrm{spark}\left(\Phi \right)\in \left[2,M+1\right]$ . Therefore, [link] yields the requirement $M\ge 2K$ .

## 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 $\Phi$   [link] . Roughly speaking, we must also ensure that $\mathcal{N}\left(\Phi \right)$ 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 $\Lambda \subset \left\{1,2,\cdots ,N\right\}$ is a subset of indices and let ${\Lambda }^{c}=\left\{1,2,\cdots ,N\right\}\setminus \Lambda$ . By ${x}_{\Lambda }$ we typically mean the length $N$ vector obtained by setting the entries of $x$ indexed by ${\Lambda }^{c}$ to zero. Similarly, by ${\Phi }_{\Lambda }$ we typically mean the $M×N$ matrix obtained by setting the columns of $\Phi$ indexed by ${\Lambda }^{c}$ to zero. We note that this notation will occasionally be abused to refer to the length $|\Lambda |$ vector obtained by keeping only the entries corresponding to $\Lambda$ or the $M×|\Lambda |$ matrix obtained by only keeping the columns corresponding to $\Lambda$ . The usage should be clear from the context, but typically there is no substantive difference between the two.

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

${∥{h}_{\Lambda }∥}_{2}\le C\frac{{∥{h}_{{\Lambda }^{c}}∥}_{1}}{\sqrt{K}}$

holds for all $h\in \mathcal{N}\left(\Phi \right)$ and for all $\Lambda$ such that $|\Lambda |\le K$ .

The NSP quantifies the notion that vectors in the null space of $\Phi$ 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 $\Lambda$ such that ${∥{h}_{{\Lambda }^{c}}∥}_{1}=0$ and hence [link] implies that ${h}_{\Lambda }=0$ as well. Thus, if a matrix $\Phi$ satisfies the NSP then the only $K$ -sparse vector in $\mathcal{N}\left(\Phi \right)$ 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 $\Delta :{\mathbb{R}}^{M}\to {\mathbb{R}}^{N}$ represent our specific recovery method. We will focus primarily on guarantees of the form

${∥\Delta ,\left(,\Phi ,x,\right),-,x∥}_{2}\le C\frac{{\sigma }_{K}{\left(x\right)}_{1}}{\sqrt{K}}$

for all $x$ , where we recall that

${\sigma }_{K}{\left(x\right)}_{p}=\underset{\stackrel{^}{x}\in {\Sigma }_{K}}{min}{∥x,-,\stackrel{^}{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 ${\ell }_{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 ${\sigma }_{K}{\left(x\right)}_{1}/\sqrt{K}$ rather than simply something like ${\sigma }_{K}{\left(x\right)}_{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 $2K$ 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 $\Phi$ must necessarily satisfy the NSP of order $2K$ .

## (theorem 3.2 of [link] )

Let $\Phi :{\mathbb{R}}^{N}\to {\mathbb{R}}^{M}$ denote a sensing matrix and $\Delta :{\mathbb{R}}^{M}\to {\mathbb{R}}^{N}$ denote an arbitrary recovery algorithm. If the pair $\left(\Phi ,\Delta \right)$ satisfies [link] then $\Phi$ satisfies the NSP of order $2K$ .

Suppose $h\in \mathcal{N}\left(\Phi \right)$ and let $\Lambda$ be the indices corresponding to the $2K$ largest entries of $h$ . We next split $\Lambda$ into ${\Lambda }_{0}$ and ${\Lambda }_{1}$ , where $|{\Lambda }_{0}|=|{\Lambda }_{1}|=K$ . Set $x={h}_{{\Lambda }_{1}}+{h}_{{\Lambda }^{c}}$ and ${x}^{\text{'}}=-{h}_{{\Lambda }_{0}}$ , so that $h=x-{x}^{\text{'}}$ . Since by construction ${x}^{\text{'}}\in {\Sigma }_{K}$ , we can apply [link] to obtain ${x}^{\text{'}}=\Delta \left(\Phi {x}^{\text{'}}\right)$ . Moreover, since $h\in \mathcal{N}\left(\Phi \right)$ , we have

$\Phi h=\Phi \left(x,-,{x}^{\text{'}}\right)=0$

so that $\Phi {x}^{\text{'}}=\Phi x$ . Thus, ${x}^{\text{'}}=\Delta \left(\Phi x\right)$ . Finally, we have that

${∥{h}_{\Lambda }∥}_{2}\le {∥h∥}_{2}={∥x,-,{x}^{\text{'}}∥}_{2}={∥x,-,\Delta ,\left(,\Phi ,x,\right)∥}_{2}\le C\frac{{\sigma }_{K}{\left(x\right)}_{1}}{\sqrt{K}}=\sqrt{2}C\frac{{∥{h}_{{\Lambda }^{c}}∥}_{1}}{\sqrt{2K}},$

where the last inequality follows from [link] .

what's a psy.d degree
Psychology Doctorate. The main difference between PsyD and PhD Psychology is that PsyD mainly focuses on clinical sessions and PhD focuses on research.
Shrajan
so most of the phd holders become professors teaching what they have learnt
Bridget
Hi, I have a question. What factors influence social facilitation and social inhibition in groups?
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.
Lametra
Lametra
Lametra
Do you know of any studies done to show social facilitation and social inhibition
Amritpal
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?
Oh wow. I never realised there was a chat on this app!
Then welcome dearest
Bridget
Thank you! ❤️
Amritpal
thank you
Ana
Hello Ana, good afternoon from here
hello im new student here.
Rai
hello
Rai
I m also student.
Rai
hi
Kavya
what is easier option to psychology?
Dhanaraj
I'm new too
Deniz
As in the the specialisation or ?
Bridget
good morning
Ana
understanding human nature is what we are going to talk about.
Ana
Philip
“ 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
Ana
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
Philip
lack determines what we will become in life?.
Ana
Not 100% but it plays a huge role
Philip
Hi! I wasn't aware there was a chat feature on this app 😊
Ophelia
👍Philip Anyaegbu
Ana
cool
Ana
👍
Ana
yes Ana I'm here
Philip
alternatively we are different, we have basic similar qualities
Bridget
Yes true Bridget.
Philip
hello there
Ciel
Hi
Philip
hi
Ej
hi
KUNDAN
hi
Ana
who we are how we think what we do insight
Ana
@ bridget. yes that's true
Ana
Ana ioanidis? do you speak Greek?
Qwanta
Qwanta no I dont speak Greek my husband does
Ana
are you a psychologist? or your husband?
Qwanta
I need some reliable informations about my studies...
Qwanta
not a psychologist
Ana
Ana
so what is the cause why a person experiences a psychological disorder if it not of their own?
it's partly genetics,culture, environment and substance abuse. generally these are the common factors which can lead to most of the disorders
war
waoo
Rai
r u proficcer
Rai
u r psychology subject
Rai
not a professor but a clinical psychologist
war
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
Astaroxche
Ana
297 according to the DSM 5
how many disorders are there
interesting question
Mahmoud
it is😅
Nelly
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.
Beenie
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
Mahmoud
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
I don't understand the question can you elaborate?
Edgar
the study of philosophy gives to the sociologist
why women are viewed as far more emotional than men?
because they actually are ,I guess.
Collins
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.
shine
sollungal bro sollungal...
Balaji
because of she has hormonal fluctuations than men..
bavi
usually women are more emotional than men and they are multi talented people
lavanya
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....
Santos
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.
Santos
y
Mahmoud
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.
Santos
Q
Mark
because women tend to be more agreeable than men.
Edgar
women at a young age are conditioned to be more in tune with emotion than man should be less
David
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.
Mehmet
The anwers are answers more to the question " Are women more emotional than men?"
Mehmet
hi are you on what'sap
no not really a fan of social laziness
Robert
huh
Parmizan
is there any way for a Btech E.C.E. graduate to take on MSC. PSYCHOLOGY
devesh
ya you can just by cracking entrance , if in India
Mansi
Any stream in UG can go for M.Sc (Psychology)
classification of traits and how they are measured
what was Freud's first name?
Sigmund
Dentriodite
sigmund
Margie
Sigismund Schlomo Freud
Sigmund Freud
Talal
sigmund
Ankita
Leon Vygotsky and Sergei Rubenstein please tell me contributions of these personalities in in 4 lines
Uzma
sigmund Freud
Harpreet
Lev Vygotsky was the founder of socio-cultural theory
Jo
So psychology was based off of the Greek gods I that right or no?
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!          