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

<p>My question is:</p>

<ol>
<li>Is this problem NP-hard?</li>
<li>If <span class="math-container">$k$</span> is a constant, <span class="math-container">$m$</span> can be unbounded, is this problem still NP-hard?</li>
<li>If it is NP-hard, what is the best (or any) approximate ratio we can achieve?</li>
</ol>

<p>Any references in the literature will also be welcome.</p>

<hr>

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

<ol>
<li>question 1 is NP-hard even for <span class="math-container">$k=m$</span>, (slightly modified) reduction from X3C as in <a href="https://www.sciencedirect.com/science/article/pii/S0304397509004101" rel="nofollow noreferrer">this paper</a></li>
<li>question 2 is still open. (I would be appropriated if one could provide any references)</li>
<li>For approximation, one can achieve the approximation ratio of
<span class="math-container">$$\frac{\left(1-\sqrt{\frac{k}{m}}\right)^2}{\left(1+\sqrt{\frac{n}{m}}\right)^2},$$</span>by <a href="https://arxiv.org/pdf/1201.0127.pdf" rel="nofollow noreferrer">this paper</a>, this gives a <span class="math-container">$\Omega\left(\frac{\epsilon m}{m+n}\right)$</span> bound for <span class="math-container">$m\ge (1+\epsilon)k$</span>. When <span class="math-container">$m=k$</span>, one can achieve <span class="math-container">$\Omega\left(\frac{1}{k(1+\epsilon)}\right)$</span> bound for any <span class="math-container">$\epsilon&gt;0$</span>, by using a local search algorithm by <a href="https://ieeexplore.ieee.org/document/8462626" rel="nofollow noreferrer">this paper</a>.</li>
<li>The hardness of approximation is unknown, even for <span class="math-container">$m=k$</span>.</li>
</ol>

CC BY-SA 3.0
2017-10-22T15:45:21.993Z
When you say "projection to the coordinates indexed by $I$", you mean coordinates of the standard basis of $\mathbb{R}^n$?
usul
CC BY-SA 3.0
2017-10-22T19:53:52.897Z
@usul yes, it is.
Paul
CC BY-SA 3.0
2017-10-26T03:46:22.727Z
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
CC BY-SA 3.0
2017-10-26T04:07:09.490Z
@NealYoung Yes, but what I need here is actually to make the smallest principal axes of the projected ellipsoid to be maximum.
Paul
CC BY-SA 3.0
2017-10-26T05:08:09.413Z
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
<np-hardness><approximation-algorithms><linear-algebra><approximation-hardness><high-dimensional-geometry>
An optimal subspace projection problem
Paul
# An optimal subspace projection problem

(Asked by: username_0 on 2017-10-22)

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](https://www.sciencedirect.com/science/article/pii/S0304397509004101)
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](https://arxiv.org/pdf/1201.0127.pdf), 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](https://ieeexplore.ieee.org/document/8462626).
4. The hardness of approximation is unknown, even for $m=k$.

**Tags:** np-hardness, approximation-algorithms, linear-algebra, approximation-hardness, high-dimensional-geometry

> **Comments:**
> **username_1**: When you say "projection to the coordinates indexed by $I$", you mean coordinates of the standard basis of $\mathbb{R}^n$?  
> **username_0**: @username_1 yes, it is.  
> **username_2**: 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$.  
> **username_0**: @NealYoung Yes, but what I need here is actually to make the smallest principal axes of the projected ellipsoid to be maximum.  
> **username_2**: 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$.  

---

## 0 answers

