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

mcq creativity involves
Sanjika
mCQ creativity involves
Sanjika
ology means a study of
is a greek word means soul
SharaAmor
science
Tina
a branch of knowledge
Kanchan
psych means soul and ology means to study.
Wajid
Can someone help me with tha latent functions of different social institutions
Usman
***interestinglydifferenttopics.blogspot.com/2020/10/reflexes-psychological-debate.html Do check this out and please correct me if I'm wrong anywhere in this
Factors that affect learning?
I am struggling with survivors guilt and complicated grief after traumatic death of spouse. how to cope.
Try to talk with someone you trust and join people who makes you feel worthy. try to help someone. Helping someone makes you feel better
sherlock
I think you must seek professional help.
I am extremely sorry for your loss...I know that the pain of your loss is overwhelming and that you are experiencing all kinds of difficult and unexpected emotions. please don't get me wrong but the best way to cope is to move on..i know its hard..but that's the only way..(continued.)
Princess
stop burdening yourself with thoughts that say you could have done something..you couldn't..your just a human being and you cant always be a superman who saves the day..please dont feel guilty when you have no reason to..(cont.)
Princess
learn to love yourself again..learn to live ..for yourself,for the people who love you and need you in their lives.live for people who you once loved...Think about how you can make your life meaningful once again.It might seem impossible but trust me its necessary ..
Princess
Let your feelings of pain out ..you dont have to suffer ..talk to people whom you trust and love. take care and have a beautiful life ahead.
Princess
First and foremost -- Wow Rowdy! You have been through a highly difficult situation in your life, hands down. As a wife, I simply cannot phathom nor imagine slightly the feelings and thoughts you bare and I'm sure as these words do not help and hit rewind; my heart and prayers are going out to you-
Stephanie
today. I will say as well, everything you are feeling and going through, please know that these feelings and thoughts are all allowed, it is okay for you to find yourself feeling or thinking things that you would never find yourself wanting especially given the situation. I'm sure you question --
Stephanie
yourself, which in turn could make you question who you are right now and what this means for you as a person now and in the future. This is all okay, but there will have to be an understanding as to how to grow from these feelings and thoughts in a more humane manner l as these feelings and ---
Stephanie
thoughts could take a turn for a much more negative outcome as you find yourself trapped in a darkness that, if strong enough, trials and tribulations take years of complex development and experience, less strong minded individuals sometimes either never find the light, or end up being stuck in ----
Stephanie
a subconscious netherworld as they are consumed given the manipulation that was not understood to overcome. It results in losing all sense of heart, faith, soul and intelligence so that you don't grow, which in your case, growth is crucial. This is what your spouse will do their best in trying -----
Stephanie
to guide you through; keep an your senses wide open so that you can learn when she is trying to communicate.
Stephanie
Angela
Thanks angela
Ali
Ali
what is this
Maryam
Geo
Geo
actually I don't know
Maryam
I badly need some for my research :<
Geo
But I need that😥
Mohammed
***courses.lumenlearning.com /boundless-sociology/chapter/theories-of-socialization/
Jobin
branches of psychology
neuropsychology
jeddy
behaviorism
Mira
Legal psychology
Miljana
Developmental psychology, Sports psychology , Clinical psychology , Marketing psychology , counseling psychology , Biological psychology, Educational psychology , Positive psychology etc.
child.psychology
Nss
social, occupational psychology
jeddy
what does it mean when the temporal lobe is anterior to occipital lobe
the cortex refers to what part of the brain
John
the cortex refers to what part of the brain
John
cerebral cortex
jeddy
behind?
jeddy
in what time of situation is training most useful?
Nyakuei
i think its not about suitation, its about the thing tatz need training.
gokul
training is possibly warranted for all situations.
rhoda
I would think that training should be an ungoing thing. That's before, during and after. just in case there's a reoccurrence
Angela
any time
Aaronz
what is Karma
I think the summation of good and bad deeds you do in your life. Accidentally or otherwise.
Yes. I totally agree.
ana
And if it is bad then the root must have been too.
ana
Yes , In Hinduism we also believe that our parent's Karma also applies to us ! Don't know about that , but it kept people in check .
Adding to Swarada point. karma can be good or bad. both will have consequences. karma is biasedness you have shown in your life. like a king could not have two rules for normal man and his son, that comes under karma.
Sujeet
Oh perfectly said!
Ok. It is also said that when one does something... bad or good..it will come back to you 10 folds of the same.
ana
yea that too ! I remember my mother always said if u stole someone's 10 rupees ur 100 will be stolen ( excuse my English ! I'm a non - English speaking person)
karma is nothing but what one usually mean when they say- what you sow, so shall you reap.
Alisha
certainly
Crazy
more important.. this concept was told by lord Krishna as part of spirituality, to focus on your good deed ,the purpose you are born for and your responsibilities. Not for hoping that bad will happen with people who made you feel bad. just giving example ;)
Sujeet
karma is the boomerang of your actions. what u put out in the universe u get back
David
Who is the founder of psychology
Wilhelm wundt
Amanda
Wilhelm Wundt
Sneha
William wundth
Ihrar
Wilhelm Wundt
Megha
and William James
Amanda
Wilhelm Wundt
Wilhelm Wundt is the founder of structuralism
Angela
Yes and also the "Father of Psychology" I think the correct word is Father not Founder.
oh ok. noted
Angela
i believe it goes beyond him I believe it is Ancient but un formalized
David
David
Oh thanks! But u summarised it well!
what is up my fellow psych peeps!!
what are some academic research on developmental psychology
Chezy
Sawrada Founder of Psychology is W.Wundt but Father of Psychology is Sigmund Freud...
Wajid
what are some good schools to study psychology?
George Mason, Penn State, UVA, university of Michigan
Jasmine
Hi I'm currently doing my experimental psychology research can you suggest a topic or research topic for my research thank you and please see 😊
Hello Jerico. I could help you out with some ideas if you're interested!
Yasmine
can u give me some ideas too?
Geo
For sure. It depends if you're trying to do an experiment (using statistics probably) or a case study what are you aiming for?
Yasmine
Hello Jerico. Try to opt for something simple and easy to do. I wouls say perhaps study the effects of color on concentration? You could get a group of people and have them take a memory test (you can find some online) in a white room for example. Then have them take another memory test
Yasmine
similar to the first one but in a different room and then you check the responses if the performance is better
Yasmine
but you have to know that a lot of factors will interfere in the performance such as mental state etc so make sure to choose a certain specific population. that's very important
Yasmine
you could be a bit more specific about it , to isolate the variables that can mess it up like age, sex, etc... you gotta take that into account
Yasmine
so that the results get somewhat accurate
Yasmine
that is very detailed information I really like it thank you very much 😊 your so very kind
Jerico
You're very welcome
Yasmine
what are your interests in general?
Yasmine
Althogh I'm persuing botany and engineering.... but I also want to study human behaviour and psychology.... I would like if anyone can share their knowledge with me !!!!
Crazy
I'm interested on effect of electroconvulsive therapy on people having a depression
Jerico
What is Electroconvulsive therapy?
Pixeled
Astral Projection
Mansi
Electroconvulsive therapy (ECT) is a medical treatment that is most commonly used in patients with severe major depression.
Jerico
What are the expected dutties functions and responsibilities of a head of an agency based on the principles, Practice of industrial psychology?
what are the psychological characteristics expected from an employee wether regular or occupying a position?
Paul
Got questions? Join the online conversation and get instant answers!