Is there a vector $y$ such that $\|P_Sy\|$ is constant for all sets $S$ of size $K$?

73 Views Asked by At

Let $\Phi\in \mathbb{R}^{m\times n}$ be a matrix with $m\leq n$ and it satisfies the restricted isometry property (RIP) of order $K>1$. Let $S\subset [n]$ be any subset of size $K$, let $\Phi_S$ be the submatrix with the columns of $\Phi$ indexed with the entries from $S$, and let us denote $P_S = \Phi_S(\Phi_S^\top\Phi_S)^{-1}\Phi_S^\top$. Also, let $\|\cdot\|$ denotes the $\ell_2$ norm. Then I have the following question:

Does there exist $y\in \mathbb{R}^m$ such that $\|P_Sy\|$ is constant for all $S\subset [n]$ such that $|S|=K$?

The intuition for this question is the following:

We can easily check that the above question has a positive answer if $\Phi$ is a unitary matrix. This follows from the observation that if $\Phi$ is unitary, we can take $y=\Phi u$, where $u=[1\quad 1\cdots 1]^\top\in \mathbb{R}^n$, so that $\|P_Sy\|^2=\|\Phi_S^\top y\|^2=\|u_S\|^2=K$. Since RIP enables a matrix to be "approximately" unitary, I was wondering if such a result should also hold when a matrix satisfies RIP. I think that if such a $y$ exists, it might be constructed using the different left eigenvectors of the submatrices $\Phi_S$ for $|S|=K$. However, it is not apparent to me how the different left eigenvectors of different $\Phi_S$ might be related to each other and how can they be combined to construct such a vector $y$.

I am not expecting a full answer, but am looking for useful comments and possible references, if there are known results about this. Any help will be much appreciated.