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.

  • $\begingroup$ When you say "projection to the coordinates indexed by $I$", you mean coordinates of the standard basis of $\mathbb{R}^n$? $\endgroup$ – usul Oct 22 '17 at 15:45
  • $\begingroup$ @usul yes, it is. $\endgroup$ – Paul Oct 22 '17 at 19:53
  • $\begingroup$ 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$. $\endgroup$ – Neal Young Oct 26 '17 at 3:46
  • $\begingroup$ @NealYoung Yes, but what I need here is actually to make the smallest principal axes of the projected ellipsoid to be maximum. $\endgroup$ – Paul Oct 26 '17 at 4:07
  • 1
    $\begingroup$ 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$. $\endgroup$ – Neal Young Oct 26 '17 at 5:08

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.