6
$\begingroup$

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$.
Improve this question
$\endgroup$
5
  • $\begingroup$ When you say "projection to the coordinates indexed by $I$", you mean coordinates of the standard basis of $\mathbb{R}^n$? $\endgroup$
    – usul
    Commented Oct 22, 2017 at 15:45
  • $\begingroup$ @usul yes, it is. $\endgroup$
    – Paul
    Commented Oct 22, 2017 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
    Commented Oct 26, 2017 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
    Commented Oct 26, 2017 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
    Commented Oct 26, 2017 at 5:08

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.