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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.