Compressed Sensing
Data Sciences Course, Jan 2015
Ramesh Hariharan
The Main Problem
- Given a $x$ of length $n$
Ramesh Hariharan
The Main Problem
Given a $x$ of length $n$
$n$ is very very large
Ramesh Hariharan
The Main Problem
Given a $x$ of length $n$
$n$ is very very large
But $x$ is known to be sparse, say $|x|_0\leq k$, i.e., at most $k$ non-0 entries
Ramesh Hariharan
The Main Problem
Given a $x$ of length $n$
$n$ is very very large
But $x$ is known to be sparse, say $|x|_0\leq k$, i.e., at most $k$ non-0 entries
What if you compress by taking $Ax$ where $A$ is $m\times n$, where $m\lt\lt n$?
Ramesh Hariharan
The Main Problem
Given a $x$ of length $n$
$n$ is very very large
But $x$ is known to be sparse, say $|x|_0\leq k$, i.e., at most $k$ non-0 entries
What if you compress by taking $Ax$ where $A$ is $m\times n$, where $m\lt\lt n$?
Can $x$ be recovered?
Ramesh Hariharan
The Main Problem
Given a $x$ of length $n$
$n$ is very very large
But $x$ is known to be sparse, say $|x|_0\leq k$, i.e., at most $k$ non-0 entries
What if you compress by taking $Ax$ where $A$ is $m\times n$, where $m\lt\lt n$?
Can $x$ be recovered?
Ramesh Hariharan
Formulating the Problem
- Given $m\times n$ matrix $A$ and given vector $b\in R^m$
Ramesh Hariharan
Formulating the Problem
Given $m\times n$ matrix $A$ and given vector $b\in R^m$
$m \lt\lt n$
Ramesh Hariharan
Formulating the Problem
Given $m\times n$ matrix $A$ and given vector $b\in R^m$
$m \lt\lt n$
Find vector $x\in R^n$ such that $Ax=b$
Ramesh Hariharan
Formulating the Problem
Given $m\times n$ matrix $A$ and given vector $b\in R^m$
$m \lt\lt n$
Find vector $x\in R^n$ such that $Ax=b$
If $A$ has rank $m$, then many solutions exist
Ramesh Hariharan
Formulating the Problem
Given $m\times n$ matrix $A$ and given vector $b\in R^m$
$m \lt\lt n$
Find vector $x\in R^n$ such that $Ax=b$
If $A$ has rank $m$, then many solutions exist
Find the sparsest of these, the one with the most 0s
Ramesh Hariharan
Formulating the Problem
Given $m\times n$ matrix $A$ and given vector $b\in R^m$
$m \lt\lt n$
Find vector $x\in R^n$ such that $Ax=b$
If $A$ has rank $m$, then many solutions exist
Find the sparsest of these, the one with the most 0s
I.e., minimize $|x|_0$
Ramesh Hariharan
The Slightly Different Optimization Criterion
- $\min |x|_0$, satisfying constraints $Ax=b$
Ramesh Hariharan
The Slightly Different Optimization Criterion
$\min |x|_0$, satisfying constraints $Ax=b$
$\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
Ramesh Hariharan
The Slightly Different Optimization Criterion
$\min |x|_0$, satisfying constraints $Ax=b$
$\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
The latter can be solved fast using linear programming
- $A(u-v)=b$
- $u,v\geq 0$
- $\min (\sum_i u_i + \sum_i v_i)$
- note $x_i$ corresponds to $u_i-v_i$, one of which is 0
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
- An example where they are different
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
- An example where they are different
- Pick two points, say $(0,100,0)$ and $(1,0,1)$
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
- An example where they are different
- Pick two points, say $(0,100,0)$ and $(1,0,1)$
- The first has smaller 0-norm, the second has smaller 1-norm
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
- An example where they are different
- Pick two points, say $(0,100,0)$ and $(1,0,1)$
- The first has smaller 0-norm, the second has smaller 1-norm
- Pick any two hyperplanes passing through both points; those are your two constraints
Ramesh Hariharan
Relationship Between the Two
- How are these two related?
- $\min |x|_0$, satisfying constraints $Ax=b$
- $\min |x|_1= \sum_i |x_i|$, satisfying constraints $Ax=b$
- An example where they are different
- Pick two points, say $(0,100,0)$ and $(1,0,1)$
- The first has smaller 0-norm, the second has smaller 1-norm
- Pick any two hyperplanes passing through both points; those are your two constraints
- $\min |x|_0\not=\min |x|_1$
Ramesh Hariharan
Sufficient Condition for Equality?
- Suppose the $x$ realizing $\min |x|_0, Ax=b$, has $|x|_0\leq k$
Ramesh Hariharan
Sufficient Condition for Equality?
Suppose the $x$ realizing $\min |x|_0, Ax=b$, has $|x|_0\leq k$
If $|Ax| \sim |x|$, $\forall x$ with $|x|_0\leq k$, then..
Ramesh Hariharan
Sufficient Condition for Equality?
Suppose the $x$ realizing $\min |x|_0, Ax=b$, has $|x|_0\leq k$
If $|Ax| \sim |x|$, $\forall x$ with $|x|_0\leq k$, then..
- Minimizing $|x|_1$ yields the same result as minimizing $|x|_0$
Ramesh Hariharan
Sufficient Condition for Equality?
Suppose the $x$ realizing $\min |x|_0, Ax=b$, has $|x|_0\leq k$
If $|Ax| \sim |x|$, $\forall x$ with $|x|_0\leq k$, then..
- Minimizing $|x|_1$ yields the same result as minimizing $|x|_0$
- Minimizing $|x|_1$ yields the same result as minimizing $|x|_0$
- Say $(1-\alpha)^2|x|^2 \leq |Ax|^2 \leq (1+\alpha)^2|x|^2$ $\forall x$ with $|x|_0\leq k$
Ramesh Hariharan
Sufficient Condition for Equality?
Suppose the $x$ realizing $\min |x|_0, Ax=b$, has $|x|_0\leq k$
If $|Ax| \sim |x|$, $\forall x$ with $|x|_0\leq k$, then..
- Minimizing $|x|_1$ yields the same result as minimizing $|x|_0$
- Minimizing $|x|_1$ yields the same result as minimizing $|x|_0$
- Say $(1-\alpha)^2|x|^2 \leq |Ax|^2 \leq (1+\alpha)^2|x|^2$ $\forall x$ with $|x|_0\leq k$
- So singular values of $A_s$ are in the range $1-\alpha\ldots 1+\alpha$ for all submatrices $A_s$ comprising $s\leq k$ columns of $A$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
- $\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$ $.........$Here $x=u-v$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$ $.........$Here $x=u-v$
= $\min_{u,v} \max_{y,a,b} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Replace\ Constraints \ with \ Objectives$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$ $.........$Here $x=u-v$
= $\min_{u,v} \max_{y,a,b} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Replace\ Constraints \ with \ Objectives$
$\geq \max_{y,a,b} \min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Flip \ Order\ and \ Next, \ Differentiate$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$ $.........$Here $x=u-v$
= $\min_{u,v} \max_{y,a,b} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Replace\ Constraints \ with \ Objectives$
$\geq \max_{y,a,b} \min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Flip \ Order\ and \ Next, \ Differentiate$
$=\max_{y} y^Tb$ subject to $y^TA+a^T={\bf 1}^T, -y^TA+b^T={\bf 1}^T, a,b\geq {\bf 0}$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$ $.........$Here $x=u-v$
= $\min_{u,v} \max_{y,a,b} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Replace\ Constraints \ with \ Objectives$
$\geq \max_{y,a,b} \min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv - y^T[A(u-v)-b]- a^Tu - b^Tv$ subject to $a,b\geq {\bf 0}$ $..................Flip \ Order\ and \ Next, \ Differentiate$
$=\max_{y} y^Tb$ subject to $y^TA+a^T={\bf 1}^T, -y^TA+b^T={\bf 1}^T, a,b\geq {\bf 0}$
$=\max_{y} y^Tb$ subject to $y^TA\leq {\bf 1}^T, y^TA\geq {\bf -1}^T$....$Simplify$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
- $\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$
Actually ${\bf =}$ $\max_{y} y^Tb$ subject to $y^TA\leq {\bf 1}^T, y^TA\geq {\bf -1}^T$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$
Actually ${\bf =}$ $\max_{y} y^Tb$ subject to $y^TA\leq {\bf 1}^T, y^TA\geq {\bf -1}^T$
Proof: Consider optimal $u,v$; remember one of $u_i,v_i=0, \forall i$
- If $\exists y$ such that ${\bf 1}^Tu+{\bf 1}^Tv=y^TA(u-v)=y^Tb$ then done
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
$\min_{u,v} {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$, $u,v\geq {\bf 0}$
Actually ${\bf =}$ $\max_{y} y^Tb$ subject to $y^TA\leq {\bf 1}^T, y^TA\geq {\bf -1}^T$
Proof: Consider optimal $u,v$; remember one of $u_i,v_i=0, \forall i$
- If $\exists y$ such that ${\bf 1}^Tu+{\bf 1}^Tv=y^TA(u-v)=y^Tb$ then done
- In other words, we want a $y$ such that $g^T=y^TA$
- Where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
- If $\exists y$ such that ${\bf 1}^Tu+{\bf 1}^Tv=y^TA(u-v)=y^Tb$ then done
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
- Prove: $\exists y$ such that $g^T=y^TA$ where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
Prove: $\exists y$ such that $g^T=y^TA$ where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
If not, then all such $g^T$'s are outside the row-space of $A$; and the set $G$ of such $g^T$'s is a convex set (a box really)
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
Prove: $\exists y$ such that $g^T=y^TA$ where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
If not, then all such $g^T$'s are outside the row-space of $A$; and the set $G$ of such $g^T$'s is a convex set (a box really)
So there exists a hyperplane $h$ containing the row-space of $A$ such that $G$ is completely on one side of $h$, i.e., $Ah=0$, and $g^Th<0, \forall g\in G$
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
Prove: $\exists y$ such that $g^T=y^TA$ where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
If not, then all such $g^T$'s are outside the row-space of $A$; and the set $G$ of such $g^T$'s is a convex set (a box really)
So there exists a hyperplane $h$ containing the row-space of $A$ such that $G$ is completely on one side of $h$, i.e., $Ah=0$, and $g^Th<0, \forall g\in G$
So $A(u-v+h)=b$ and ${\bf 1}^Tu+{\bf 1}^Tv+g^Th<{\bf 1}^Tu+{\bf 1}^Tv$, a contradiction
Ramesh Hariharan
Certificate of Optimality for $\min |x|_1$: LP Duality
Prove: $\exists y$ such that $g^T=y^TA$ where $g_i=sgn(u_i-v_i)$ except if $u_i=v_i=0$ in which case $-1\leq g_i\leq 1$
If not, then all such $g^T$'s are outside the row-space of $A$; and the set $G$ of such $g^T$'s is a convex set (a box really)
So there exists a hyperplane $h$ containing the row-space of $A$ such that $G$ is completely on one side of $h$, i.e., $Ah=0$, and $g^Th<0, \forall g\in G$
So $A(u-v+h)=b$ and ${\bf 1}^Tu+{\bf 1}^Tv+g^Th<{\bf 1}^Tu+{\bf 1}^Tv$, a contradiction
Ramesh Hariharan
Summarizing
- We want $\min |x|_0$ subject to $Ax=b$
Ramesh Hariharan
Summarizing
We want $\min |x|_0$ subject to $Ax=b$
Instead we do $\min |x|_1$ subject to $Ax=b$, using LP $\min {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$
Ramesh Hariharan
Summarizing
We want $\min |x|_0$ subject to $Ax=b$
Instead we do $\min |x|_1$ subject to $Ax=b$, using LP $\min {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$
Claim: If $(1-\alpha)^2|x|^2 \leq |Ax|^2 \leq (1+\alpha)^2|x|^2$, $\forall$ $x$ with $|x|_0\leq k$ then...
Ramesh Hariharan
Summarizing
We want $\min |x|_0$ subject to $Ax=b$
Instead we do $\min |x|_1$ subject to $Ax=b$, using LP $\min {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$
Claim: If $(1-\alpha)^2|x|^2 \leq |Ax|^2 \leq (1+\alpha)^2|x|^2$, $\forall$ $x$ with $|x|_0\leq k$ then...
- Suppose the $|x|_0$ optimum $x$ has $|x|_0= s< k$ ; there exists $y$ such that $y^TA=g^T$, where $g_i=sgn(x_i)$ (with exceptions if $x_i=0$)
Ramesh Hariharan
Summarizing
We want $\min |x|_0$ subject to $Ax=b$
Instead we do $\min |x|_1$ subject to $Ax=b$, using LP $\min {\bf 1}^Tu+{\bf 1}^Tv$ subject to $A(u-v)=b$
Claim: If $(1-\alpha)^2|x|^2 \leq |Ax|^2 \leq (1+\alpha)^2|x|^2$, $\forall$ $x$ with $|x|_0\leq k$ then...
Suppose the $|x|_0$ optimum $x$ has $|x|_0= s< k$ ; there exists $y$ such that $y^TA=g^T$, where $g_i=sgn(x_i)$ (with exceptions if $x_i=0$)
It follows that $\min |x|_0 = \min |x|_1$ subject to $Ax=b$
Ramesh Hariharan
Determining $y$
- Let $_s$ denote the $s$ indices corresponding to non-zero values of the optimum 0-norm solution $x$; $\overline{s}$ denote the indices in complement.
Ramesh Hariharan
Determining $y$
Let $_s$ denote the $s$ indices corresponding to non-zero values of the optimum 0-norm solution $x$; $\overline{s}$ denote the indices in complement.
We want $y$ such that $y^TA_s=g^T=sgn(x_s^T)$
Ramesh Hariharan
Determining $y$
Let $_s$ denote the $s$ indices corresponding to non-zero values of the optimum 0-norm solution $x$; $\overline{s}$ denote the indices in complement.
We want $y$ such that $y^TA_s=g^T=sgn(x_s^T)$
And then $y^TA_{\overline{s}}$ must have all entries between -1 and 1
Ramesh Hariharan
Determining $y$
Let $_s$ denote the $s$ indices corresponding to non-zero values of the optimum 0-norm solution $x$; $\overline{s}$ denote the indices in complement.
We want $y$ such that $y^TA_s=g^T=sgn(x_s^T)$
And then $y^TA_{\overline{s}}$ must have all entries between -1 and 1
$A_s$ has rank $s$, otherwise there exists $x$, $|x|_0< s$, $Ax=b$
Ramesh Hariharan
Determining $y$
Let $_s$ denote the $s$ indices corresponding to non-zero values of the optimum 0-norm solution $x$; $\overline{s}$ denote the indices in complement.
We want $y$ such that $y^TA_s=g^T=sgn(x_s^T)$
And then $y^TA_{\overline{s}}$ must have all entries between -1 and 1
$A_s$ has rank $s$, otherwise there exists $x$, $|x|_0< s$, $Ax=b$
So possibly many solutions to $y^TA_s=g^T$
Ramesh Hariharan
Solving for $y$
- Find $y$ such that $y^TA_s=g^T$
Ramesh Hariharan
Solving for $y$
Find $y$ such that $y^TA_s=g^T$
$A_s=U\Sigma V^T$: $U=m\times s$, $\Sigma=s\times s$, $V=s\times s$, $VV^T=V^TV=I$, $U^TU=I$
Ramesh Hariharan
Solving for $y$
Find $y$ such that $y^TA_s=g^T$
$A_s=U\Sigma V^T$: $U=m\times s$, $\Sigma=s\times s$, $V=s\times s$, $VV^T=V^TV=I$, $U^TU=I$
Find $y$ such that $y^T (U\Sigma V^T)=g^T$
Ramesh Hariharan
Solving for $y$
Find $y$ such that $y^TA_s=g^T$
$A_s=U\Sigma V^T$: $U=m\times s$, $\Sigma=s\times s$, $V=s\times s$, $VV^T=V^TV=I$, $U^TU=I$
Find $y$ such that $y^T (U\Sigma V^T)=g^T$
Instead, find $y$ such that $y^T (U\Sigma V^T)(V\Sigma^{-1}U^T) =g^T(V\Sigma^{-1} U^T)$
Ramesh Hariharan
Solving for $y$
Find $y$ such that $y^TA_s=g^T$
$A_s=U\Sigma V^T$: $U=m\times s$, $\Sigma=s\times s$, $V=s\times s$, $VV^T=V^TV=I$, $U^TU=I$
Find $y$ such that $y^T (U\Sigma V^T)=g^T$
Instead, find $y$ such that $y^T (U\Sigma V^T)(V\Sigma^{-1}U^T) =g^T(V\Sigma^{-1} U^T)$
- Good unless $y^TA_s-g^T$ is non-zero and orthogonal to the columns of $V\Sigma^{-1}U^T$, need to keep this in mind
- Good unless $y^TA_s-g^T$ is non-zero and orthogonal to the columns of $V\Sigma^{-1}U^T$, need to keep this in mind
Ramesh Hariharan
Solving for $y$
Find $y$ such that $y^TA_s=g^T$
$A_s=U\Sigma V^T$: $U=m\times s$, $\Sigma=s\times s$, $V=s\times s$, $VV^T=V^TV=I$, $U^TU=I$
Find $y$ such that $y^T (U\Sigma V^T)=g^T$
Instead, find $y$ such that $y^T (U\Sigma V^T)(V\Sigma^{-1}U^T) =g^T(V\Sigma^{-1} U^T)$
- Good unless $y^TA_s-g^T$ is non-zero and orthogonal to the columns of $V\Sigma^{-1}U^T$, need to keep this in mind
- Good unless $y^TA_s-g^T$ is non-zero and orthogonal to the columns of $V\Sigma^{-1}U^T$, need to keep this in mind
So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
Ramesh Hariharan
Psudeo-Inverse, and One Solution for $y$
- So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
Ramesh Hariharan
Psudeo-Inverse, and One Solution for $y$
So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
If $y$ is in the column space of $U$ then $y^T U U^T=y^T=g^T(V\Sigma^{-1} U^T)$
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
Ramesh Hariharan
Psudeo-Inverse, and One Solution for $y$
So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
If $y$ is in the column space of $U$ then $y^T U U^T=y^T=g^T(V\Sigma^{-1} U^T)$
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
So of the many $y$'s, let's take the (unique) one in the column space of $U$.
Ramesh Hariharan
Psudeo-Inverse, and One Solution for $y$
So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
If $y$ is in the column space of $U$ then $y^T U U^T=y^T=g^T(V\Sigma^{-1} U^T)$
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
So of the many $y$'s, let's take the (unique) one in the column space of $U$.
Verify $y^TA_s-g^T= g^T(V\Sigma^{-1} U^T)(U\Sigma V^T)-g^T=g^TVV^T-g^T=0$
Ramesh Hariharan
Psudeo-Inverse, and One Solution for $y$
So solve for $y$ in $y^T U U^T = g^T(V\Sigma^{-1} U^T)$
If $y$ is in the column space of $U$ then $y^T U U^T=y^T=g^T(V\Sigma^{-1} U^T)$
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
- $V\Sigma^{-1} U^T$ behaves like an inverse in this case!
So of the many $y$'s, let's take the (unique) one in the column space of $U$.
Verify $y^TA_s-g^T= g^T(V\Sigma^{-1} U^T)(U\Sigma V^T)-g^T=g^TVV^T-g^T=0$
Conclusion: $y^T=g^T(V\Sigma^{-1} U^T)$
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
- Let $A_t$ denote all columns of $A_s$ plus one column of $A_{\overline{s}}$; this extra column can be written as $A_te$, $|e|_0=1$
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
- Let $A_t$ denote all columns of $A_s$ plus one column of $A_{\overline{s}}$; this extra column can be written as $A_te$, $|e|_0=1$
- We want $g^T(V\Sigma^{-1} U^T)A_te$ to have entries between -1 and 1
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
- Let $A_t$ denote all columns of $A_s$ plus one column of $A_{\overline{s}}$; this extra column can be written as $A_te$, $|e|_0=1$
We want $g^T(V\Sigma^{-1} U^T)A_te$ to have entries between -1 and 1
$g^T(V\Sigma^{-1} [\Sigma^{-1} V^TV \Sigma] U^T)A_te=g^T(V\Sigma^{-2}V^T) A_s^TA_te$
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
- Let $A_t$ denote all columns of $A_s$ plus one column of $A_{\overline{s}}$; this extra column can be written as $A_te$, $|e|_0=1$
We want $g^T(V\Sigma^{-1} U^T)A_te$ to have entries between -1 and 1
$g^T(V\Sigma^{-1} [\Sigma^{-1} V^TV \Sigma] U^T)A_te=g^T(V\Sigma^{-2}V^T) A_s^TA_te$
$|g|^2=s$, $|z^T|^2=|g^TV\Sigma^{-2} V^T|^2\in \frac{s}{(1\pm \alpha)^4} $, $z^TA_s^T=h^TA_t^T$ where $h^T=[z^T \ \ \ 0]$
Ramesh Hariharan
What's Left?
- We need $y^TA_{\overline{s}}$ to have all entries between -1 and 1
- Let $A_t$ denote all columns of $A_s$ plus one column of $A_{\overline{s}}$; this extra column can be written as $A_te$, $|e|_0=1$
We want $g^T(V\Sigma^{-1} U^T)A_te$ to have entries between -1 and 1
$g^T(V\Sigma^{-1} [\Sigma^{-1} V^TV \Sigma] U^T)A_te=g^T(V\Sigma^{-2}V^T) A_s^TA_te$
$|g|^2=s$, $|z^T|^2=|g^TV\Sigma^{-2} V^T|^2\in \frac{s}{(1\pm \alpha)^4} $, $z^TA_s^T=h^TA_t^T$ where $h^T=[z^T \ \ \ 0]$
TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
- Does transformation by $A$ preserve near-orthogonality?
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Does transformation by $A$ preserve near-orthogonality?
Let $A_t=X\Pi Y^T$; since $t\leq k$, items in $\Pi$ $\in (1\pm\alpha)$
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Does transformation by $A$ preserve near-orthogonality?
Let $A_t=X\Pi Y^T$; since $t\leq k$, items in $\Pi$ $\in (1\pm\alpha)$
- $h^TA_t^TA_te=h^TY\Pi^2Y^Te= (Y^Th)^T\Pi^2 (Y^Te)$ where $Y^Th$ and $Y^Te$ are mutually orthogonal
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Does transformation by $A$ preserve near-orthogonality?
Let $A_t=X\Pi Y^T$; since $t\leq k$, items in $\Pi$ $\in (1\pm\alpha)$
- $h^TA_t^TA_te=h^TY\Pi^2Y^Te= (Y^Th)^T\Pi^2 (Y^Te)$ where $Y^Th$ and $Y^Te$ are mutually orthogonal
- What happens to the dot-prod of two orthogonal vectors if we scale each vector by $1\pm \alpha$? Of course, $0\leq \alpha<1$.
Ramesh Hariharan
Showing $-1\leq y^TAe\leq 1$
- TPT $hA_t^TA_te$ entries $\in [-1,1]$, $|h|^2 \in \frac{s}{(1\pm \alpha)^4},|e|^2=1,h^Te=0$
Does transformation by $A$ preserve near-orthogonality?
Let $A_t=X\Pi Y^T$; since $t\leq k$, items in $\Pi$ $\in (1\pm\alpha)$
- $h^TA_t^TA_te=h^TY\Pi^2Y^Te= (Y^Th)^T\Pi^2 (Y^Te)$ where $Y^Th$ and $Y^Te$ are mutually orthogonal
What happens to the dot-prod of two orthogonal vectors if we scale each vector by $1\pm \alpha$? Of course, $0\leq \alpha<1$.
in absolute value, at most $2\alpha |h||e|\leq 2\alpha \frac{\sqrt{s}}{(1\pm \alpha)^2}\leq 1$, for $\alpha = \frac{1}{3\sqrt{s}}$...DONE
Ramesh Hariharan
What types of $A$ are Length Preserving for Sparse Vectors?
We want $(1-\frac{1}{3\sqrt{s}})^2\leq |Ax|^2\leq (1+\frac{1}{3\sqrt{s}})^2$, $\forall x$ with $|x|_0= s+1$, $\forall s < k$
By JL theorem, we know that a $m\times n$ random Gaussian matrix with mean 0, variance $\frac{1}{m}$ Gaussian entries chosen independently are length-preserving
Show that for $m = \Omega(k^2\log n)$ what we want holds!
Ramesh Hariharan
Share