# An optimal subspace projection problem

Suppose we have a $k$-dimensional subspace $V$ in $\mathbb{R}^n$ given by a basis $\{v_1,\cdots,v_k\in \mathbb{R}^n\}$, find an index set $I\subset [n]$ with $|I|=m$ where $k\le m\le n$, such that $$\max_{v\in V}\frac{||v||_2}{||v_I||_2}$$ is minimum, where $v_I\in \mathbb{R}^m$ is the projection of $v$ to the coordinates indexed by $I$.

My question is:

1. Is this problem NP-hard?
2. If $k$ is a constant, $m$ can be unbounded, is this problem still NP-hard?
3. If it is NP-hard, what is the best (or any) approximate ratio we can achieve?

Any references in the literature will also be welcome.

• When you say "projection to the coordinates indexed by $I$", you mean coordinates of the standard basis of $\mathbb{R}^n$? – usul Oct 22 '17 at 15:45
• @usul yes, it is. – Paul Oct 22 '17 at 19:53
• Is this equivalent to the following problem? Given a $k$-dimensional sphere $S_k$ in $\mathbb{R}^n$, find an index set $I$ of size $m$ so that the projection of $S_k$ onto $\mathbb{R}^n_I$ has minimum diameter, where $\mathbb{R}^n_I$ is the linear subspace spanned by the $m$ axes with coordinate indices in $I$. – Neal Young Oct 26 '17 at 3:46
• @NealYoung Yes, but what I need here is actually to make the smallest principal axes of the projected ellipsoid to be maximum. – Paul Oct 26 '17 at 4:07
• Isn't that the same in the following sense (keeping in mind that we restrict to $v$ with $\|v\|_2=1$)? $J$ minimizes the diameter of the projection of $S_k$ onto $\mathbb{R}^n_J$ if and only if $I = [n]\setminus J$ maximizes the length of the smallest principal axis of the projection of $S_k$ onto $\mathbb{R}^n_I$. – Neal Young Oct 26 '17 at 5:08