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

Edit: This problem is equivalent to the following submatrix selection problem: let $$V$$ be a $$k\times n$$ matrix such that the row vectors of $$V$$ are orthonormal, find a submatrix $$V'$$ of $$V$$ by selecting $$m$$ columns from $$V$$, such that $$\sigma_{\min}(V')\text{ is maximum},$$ where $$\sigma_{\min}$$ is the smallest singular value. Follows are (partial) answers to the question:

1. question 1 is NP-hard even for $$k=m$$, (slightly modified) reduction from X3C as in this paper
2. question 2 is still open. (I would be appropriated if one could provide any references)
3. For approximation, one can achieve the approximation ratio of $$\frac{\left(1-\sqrt{\frac{k}{m}}\right)^2}{\left(1+\sqrt{\frac{n}{m}}\right)^2},$$by this paper, this gives a $$\Omega\left(\frac{\epsilon m}{m+n}\right)$$ bound for $$m\ge (1+\epsilon)k$$. When $$m=k$$, one can achieve $$\Omega\left(\frac{1}{k(1+\epsilon)}\right)$$ bound for any $$\epsilon>0$$, by using a local search algorithm by this paper.
4. The hardness of approximation is unknown, even for $$m=k$$.
• 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