Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix

Introduction

From a conceptual point of view, rather than interpreting a matrix as a block of numbers, we view it as a set of vectors (specifically, column vectors) which are indivisible entities. Thus, the formalization of “significant information” is essentially related to finding a subset of columns of the matrix which satisfies some certain spectral conditions or orthogonality requirements. From a purely combinatorial perspective, treating vectors as elements of a set, one can also view subset selection in matrices as a generalization of the usual subset selection problem where the elements contain little or no information. To give a specific example, the well known Set Cover problem asks for a smallest cardinality subset of a set system which covers a universal set. Likewise, the problem we are interested in essentially asks for a small number of column vectors to “cover” the whole matrix. In this paper, we state a measure of quality for this problem, namely the volume, and we prove an exponential inapproximability result for the problem of selecting a maximum volume sub-matrix of a matrix.

Several problems in matrix analysis require to construct a more concise version of a matrix generally performed by a re-ordering of the columns , such that the new smaller matrix is as good a representative of the original as possible. One of the criteria that defines the quality of a subset of columns of a matrix is how well-conditioned the sub-matrix that they define is. To motivate the discussion, consider the set of three vectors

which are clearly dependent, and any two of which are a basis. Thus any pair can serve to reconstruct all vectors. Suppose we choose $e_{1},u$ as the basis, then $e_{2}=(1/\epsilon)u-(\sqrt{1-\epsilon^{2}}/{\epsilon})e_{1}$, and we have a numerical instability in this representation as $\epsilon\rightarrow 0$. Such problems get more severe as the dimensionality of the space gets large (curse of dimensionality), and it is natural to ask the representatives to be “as far away from each other as possible”. From this simple example, we see that two orthogonal vectors will capture more information about a superset of columns than two that have an acute angle between each other. Hence, in its generality, this vaguely stated problem can be stated as finding a subset of columns with the maximum volume possible or equivalently with the maximum determinant. A similar (but not equivalent) problem is to find a subset with the maximum smallest singular value. Indeed, in one of the early works studying Rank Revealing QR (RRQR) factorizations , while discussing different options on how to choose a good sub-matrix, it was noted that it turns out that “the selection of the sub-matrix with the maximum smallest singular value suggested in can be replaced by the selection of a sub-matrix with maximum determinant”, which heuristically proposes to maximize the volume of the sub-matrix instead of using more complicated functions. Several algorithms have been designed following this intuition . The optimization problem of finding a maximum volume sub-matrix of a matrix was only recently studied by Çivril and Magdon-Ismail:

MAX-VOL is NP-hard. Further, it is NP-hard to approximate to within $2\sqrt{2}/3+\epsilon$ for arbitrarily small $\epsilon>0$.

Since MAX-VOL is NP-hard, it is natural to ask for an algorithm to approximate the maximum volume. The first thing one might try is a simple greedy algorithm for approximating MAX-VOL:

The analysis of the approximation ratio of this algorithm and a lower bound was also provided in . Specifically, let $Vol(Gr)$ be the volume of the column vectors chosen by Greedy and let $Vol(Opt)$ be the optimum volume. Then, we have

There exists an instance of MAX-VOL for which $Vol(Gr)\leq\frac{1}{2^{k-1}}(1-\epsilon)\cdot Vol(Opt)$ for arbitrarily small $\epsilon>0$. Furthermore, this instance can explicitly be constructed.

Note that there is a gap between the proven approximation ratio and the lower bound implied by the explicit example. The analysis yielding the ratio $1/k!$ is essentially a product of $k$ different mutually exclusive analyses related to each step of the algorithm. However, it is not clear whether the overall contribution of these different steps to the approximation ratio is actually better than their products. Indeed, the lower bound of $1/2^{k-1}$ pertains to such a peculiar construction that we have conjectured a $1/2^{k-1}$ approximation ratio for the greedy algorithm. Hence, in general, proving an exponential inapproximability for this problem is an important step towards characterizing its approximability properties. It will show that the greedy algorithm is almost the best one can hope for.

This work takes a first step towards this goal and prove exponential inapproximability for MAX-VOL via a gap preserving reduction from the well known Label-Cover problem using the Parallel Repetition Theorem . In doing so, we will establish that the greedy algorithm is asymptotically optimal up to a logarithm in the exponent. Specifically, we prove the following theorem:

There exists $\delta<1$ and $c>0$ such that the problem MAX-VOL is not approximable within $2^{-ck}$ for $k=\delta n$, unless $P=NP$.

Our reduction may also be of independent interest which can be used to prove inapproximability results for other matrix approximation problems with different objective functions.

We introduce some preliminary notation and definitions. Let a matrix $A$ be given in column notation as: $A=\{v_{1},v_{2},\ldots,v_{n}\}$. The volume of $A$, $Vol(A)$ can be recursively defined as follows: if A contains one column, i.e. $A=\{v_{1}\}$, then $Vol(A)={\|v\|}_{2}$, where ${\|\cdot\|}_{2}$ is the Euclidean norm. If A has more than one column, $Vol(A)={\|v-\pi_{(A-\{v\})}(v)\|}_{2}\cdot Vol(A-\{v\})$ for any $v\in A$, where $\pi_{A}(v)$ is the projection of $v$ onto the space spanned by the column vectors of $A$. It is well known that $\pi_{(A-\{v\})}(v)=A_{v}A_{v}^{+}v$, where $A_{v}$ is the matrix whose columns are the vectors in $A-\{v\}$, and $A_{v}^{+}$ is the pseudo-inverse of $A_{v}$ (see for example ). Using this recursive expression, we have

where $A_{i}=\{v_{1}\cdots v_{i}\}$ for $\leq i\leq n-1$.

We observe a simple fact about the “distance” of a vector to a subspace in the following lemma, which will be useful in the final proof. Given two sets of vectors $P$ and $Q=\{q_{1},\ldots,q_{m}\}$, let $d(q,P)={\|q-\pi_{P}(q)\|}_{2}$ denote the distance of $q\in Q$ to the space spanned by the vectors in $P$.

$Vol(P\cup Q)\leq Vol(P)\cdot\prod_{i=1}^{n}d(q_{i},P)$.

We argue by induction on $m$. For $m=1$, $Q$ has one element and the statement trivially holds. Assume that it is true for $n=k$ where $Q=\{q_{1},\ldots,q_{k}\}$. Then, for any $q_{k+1}$

(a) follows because $d(q,A\cup B)\leq d(q,A)$ for any $A$, $B$ and (b) follows by the induction hypothesis. ∎

2 Related Work

The concept of volume has been closely related to matrix approximation and mainly studied from a linear algebraic perspective. There are a few results revealing the relationship between the volume of a subset of columns of a matrix and its approximation. In , the authors introduced volume sampling to find low-rank approximation to a matrix where one picks a subset of columns with probability proportional to the volume of the simplex they define. In volume sampling, one picks a subset of columns $S$ of size $k$ with probability

Thus, not only is sampling larger volume columns good, but approximately sampling columns with large volume can prove useful for matrix approximation. A natural question is to ask what happens when one finds a set of columns with the largest volume (deterministic), which is our problem MAX-VOL. Note that, the last expression (1) is reminiscent of the approximation ratio we have proved for MAX-VOL in , but its analysis relies on a linear algebraic identity whereas the result in is derived via combinatorial means. MAX-VOL and volume sampling seem to be related, but they have different characteristics. MAX-VOL is proven to be intractable by using complexity theoretic tools, whereas according to a recent result by Deshpande and Rademacher , volume sampling can be exactly implemented in polynomial time. This work together with reveals the fact that, although one can exactly sample the columns of a matrix with probability proportional to their volumes, identifying a subset with the maximum volume is hard.

Goreinov and Tyrtyshnikov provided explicit statements of how MAX-VOL, in particular, is related to low-rank approximations in the following theorem:

Suppose that $A$ is an $m\times n$ block matrix of the form

where $A_{11}$ is nonsingular, $k\times k$, whose volume is at least $\mu^{-1}$ times the maximum volume among all $k\times k$ sub-matrices. Then $\|B\|_{\infty}$ denotes the maximum modulus of the entries of a matrix $B$. $\|A_{22}-A_{21}A_{11}^{-1}A_{12}\|_{\infty}\leq\mu(k+1)\sigma_{k+1}(A)$.

This theorem implies that if one has a good approximation to the maximum volume $k\times k$ sub-matrix, then the rows and columns corresponding to this sub-matrix can be used to obtain a good approximation to the entire matrix in the $\infty$-norm. If $\sigma_{k+1}(A)$ is small for some small $k$, then this yields a low-rank approximation to $A$. also proves a similar result to Theorem 1.7.

Pan unifies the main approaches developed for finding RRQR factorizations by defining the concept of local maximum volume and then gives a theorem relating it to the quality of approximation.

we have $\sigma_{min}(R_{11})\geq(1/\sqrt{k(n-k)\,\mu^{2}+1})\sigma_{k}(A)$ and $\sigma_{1}(R_{22})\leq\sqrt{k(n-k)\,\mu^{2}+1}\,\sigma_{k+1}(A)$.

We note that, MAX-VOL asks for a stronger property of the set of vectors to be chosen, i.e. it asks for a “good” set of vectors in a global sense rather than only requiring local optimality. Obviously, a solution to MAX-VOL provides a set of vectors with local maximum volume.

Independently of our work, there are some results in computational geometry which are related to the ability to construct large simplices embedded in V-polytopes. Essentially, the problem we consider is a more general version of finding a large simplex in a V-polytope, where the vertices of the polytope are the column vectors. The results in this area are similar to ours in spirit but using different techniques . The most relevant work to ours is that of Koutis , which shows exponential inapproximability for finding a large simplex in a V-polytope. He provides a reduction from set packing using an inapproximability result of , whereas our reduction is directly from the Label Cover problem.

The Label-Cover Problem

Our reduction will be from the Label Cover problem. Label Cover combinatorially captures the expressive power of a 2-prover 1-round proof system for the problem Max-3SAT(5). Specifically, there exists a reduction from Max-3SAT(5) to Label Cover, so that using the well known parallel repetition technique for the specified proof system yields a new $k$-fold Label Cover instance. For simplicity, we prefer to state our reduction from Label Cover and for the sake of completeness, we provide a canonical reduction from Max-3SAT(5) to Label Cover.

Max-3SAT(5) is defined as follows: Given a set of $5n/3$ variables and $n$ clauses in conjunctive normal form where each clause contains three distinct variables and each variable appears in exactly five clauses, find an assignment of variables such that it maximizes the fraction of satisfied clauses. The following result is well known :

There is a constant $\epsilon>0$, such that it is NP-hard to distinguish between the instances of Max-3SAT(5) having optimal value $1$ and optimal value at most $(1-\epsilon)$.

Although this result was proved for general 3CNF formulas, without the requirement that each variable appears exactly $5$ times, there is a standard reduction from Max-3SAT to Max-3SAT(5) , which only results in a difference in the constant $\epsilon$.

A Label Cover instance $L$ is defined as follows:

$G(V,W,E)$ is a regular bipartite graph with vertex sets $V$ and $W$, and the edge set $E$.

$\Sigma_{V}$ and $\Sigma_{W}$ are the label sets associated with $V$ and $W$, respectively.

$\Pi$ is the collection of constraints on the edge set, where the constraint on an edge $e$ is defined as a function $\Pi_{e}:\Sigma_{V}\rightarrow\Sigma_{W}$.

A labeling is an assignment to the vertices of the graph, $\sigma:\{V\rightarrow\Sigma_{V}\}\cup\{W\rightarrow\Sigma_{W}\}$. It is said to satisfy an edge $e=(v,w)$ if $\Pi_{e}(\sigma(v))=\sigma(w)$. The Label Cover problem asks for an assignment $\sigma$ such that the fraction of the satisfied edges is maximum.

A standard reduction from Max-3SAT(5) to Label Cover reveals that

There is a constant $\epsilon^{\prime}>0$, such that it is NP-hard to distinguish between the instances of Label Cover having optimal value $1$ and optimal value at most $(1-\epsilon^{\prime})$.

Exponential Inapproximability of MAX-VOL

At the heart of our analysis is a set of vectors with a special property. We will use a set of vectors (composed of binary entries for simplicity of construction) such that any two of them have large dot-product. We will also require that the dot product of a vector and the binary complement of any other vector is large. More specifically, we need these dot products be proportional to the Euclidean norms squared of the vectors.

Given a vector $v=(v_{1}\ldots v_{m})$ where $v_{i}\in\{0,1\}$ for $m\geq i\geq 1$, we denote the binary complement of $v$ by $\overline{v}=(\overline{v_{1}}\ldots\overline{v_{m}})$ where $\overline{v_{i}}=1$ if $v_{i}=0$, and $\overline{v_{i}}=0$ otherwise. We begin with the following lemma:

For $m\geq 2$, there exists a set of vectors $B=\{b_{1},\ldots,b_{2^{m}-1}\}$ of dimension $2^{m}$ with binary entries such that the following three conditions hold:

${\|b_{i}\|}_{2}=2^{(m-1)/2}$ for $2m-1\geq i\geq 1$

$b_{i}\cdot\overline{b_{j}}=2^{m-2}$ for $2m-1\geq i>j\geq 1$.

$b_{i}\cdot b_{j}=2^{m-2}$ for $2m-1\geq i>j\geq 1$.

Consider the Hadamard matrix $H$ of dimension $2^{m}\times 2^{m}$ with entries $-1$ and $1$, constructed recursively by Sylvester’s method. Let $B$ be the $(2^{m}-1)\times 2^{m}$ matrix consisting of the rows of $H$ for which we replace $-1$’s with ’s, excluding the all $1$’s row. We claim that the rows of $B$ satisfy the requirements. Indeed, by the properties of Hadamard matrices, each row of $B$ has exactly $2^{m-1}$ $1$’s which satisfies the first requirement. Note also that, for $m\geq 2$, two distinct rows of $H$ (excluding the all $1$’s vector) have exactly $2^{m-2}$ element-wise dot-products of the following four types: $1\cdot 1$, $1\cdot(-1)$, $(-1)\cdot 1$, $(-1)\cdot(-1)$. Considering the construction of $B$, we have that the dot-product of any two of its rows is $2^{m-2}$ since all the products in $H$ involving $-1$ vanishes for $B$. Similarly the dot-product of a row with the binary complement of another row is $2^{m-2}$ by symmetry. Thus, the second and the third requirement also hold. ∎

2 The Reduction

3 Analysis

We start with the completeness of the reduction:

which implies $d_{V_{C}}\leq ck/(1-\log{3}/2)<5ck$ since $\log{3}<1.6$. The analysis for $d_{W_{C}}$ along exactly the same lines also yields $d_{W_{C}}<5ck$. Noting the expressions for $c$ and $k$, and following the definitions, we obtain

Claim 3.5 ensures that if the volume of a set of $k$ vectors exceeds $2^{-ck}$, then some certain concentration result should hold, namely Equation (3) and Equation (4). We will now show that, these equations imply $Vol(C)<2^{-ck}$ which is our contradiction.

We now give an upper bound for the distance of the vectors in $Q$ to $P$, namely ${\|A_{v_{s},i_{s}}-\pi_{P}(A_{v_{s},i_{s}})\|}_{2}$ for each $A_{v_{s},i_{s}}\in Q$. To this end, we define the set $N(A_{v_{s},i_{s}})=\{C_{w}|e=(A_{v_{s},i_{s}},w)\text{ is unsatisfied}\}$. Note that the vectors in different sets are mutually orthogonal, and by the reduction we have

for $A_{w,j}\in N(A_{v_{s},i_{s}})$ since $e=(A_{v_{s},i_{s}},A_{w,j})$ is unsatisfied. Thus, by the Pythagoras Theorem, we obtain

Noting that $\log{e}\geq 10/7$, we obtain $\log{e}\cdot(1-2\epsilon_{1})\geq 10/7\cdot 7/10=1$. Then, we get

where $e$ is the base of the natural logarithm. In the second inequality, we have used the fact that $Vol(P)\leq 1$ and $(1-\frac{1}{t})^{t}\leq e^{-1}$ for $t>1$.

if the optimal value of the Label Cover instance is $1$, then the optimal value of the MAX-VOL instance is $1$.

if $\phi$ is satisfiable , then $OPT(\text{MAX-VOL})=1$.

if $\phi$ is not satisfiable , then $OPT(\text{MAX-VOL})<2^{-ck}$.

Thus, unless $P=NP$, MAX-VOL is inapproximable within $2^{-ck}$ for some constant $c>0$.

Discussion

Our reduction heavily relies on the Raz’ Parallel Repetition Theorem . Indeed, it doesn’t seem possible to get an exponential inapproximability result without parallel repetition. But, since the degrees of the vertices in the Label-Cover instance exponentially increases with respect to the number of repetitions, our constant $c$ depends on the constant $\alpha$ in Raz’ result. It might be possible to improve this constant by making use of more sophisticated parallel repetition theorems, but we did not proceed so far. Indeed, the exact analysis is irrelevant as the constant will be too small in all cases. Overall, the strength of our result is is directly related to the underlying theorems for the inapproximability of Label-Cover.

Another way of getting a stronger hardness result is to find a more sophisticated reduction. In our MAX-VOL instance, the subspaces “reserved” for each edge in the Label-Cover instance are orthogonal to each other. This dramatically simplifies the analysis, yielding perfect completeness, i.e. volume $1$ in MAX-VOL. It might be possible to construct a MAX-VOL instance for which these subspaces have some pair-wise angle, so that we sacrifice the perfect completeness, but at the same time get a much smaller soundness. This would improve the inapproximability result.

The obvious open problem is whether the inapproximability can be strengthened to $2^{-k+1}$. Recall that this is the lower bound for the greedy algorithm for MAX-VOL. Considering the multiplicative nature of the problem yielding a very small approximation ratio for the obvious greedy algorithm, a significant improvement of the upper bound would be expected to provide asymptotically better approximations in the exponent. This suggests that the inherent hardness of MAX-VOL might be very close to the performance of the greedy algorithm. However, with the techniques we have used, it is not possible to break the dependence of $c$ on the constant in the parallel repetition theorems.

We would finally like to point out that the reduction and the analysis provided in this paper might be a good starting point for studying hardness of other matrix approximation problems in general (e.g. ) for which no technique related to the PCP theorem have been used. Such an extension to other matrix approximation problems is not trivial. Indeed, computing the volume is already difficult although purely geometric intuition is used. Relating this to other linear algebraic functions (e.g. singular values) which continuously depend on the entries will put even more strain on the analysis.

Acknowledgments: We would like to thank Ioannis Koutis who, in the final stages of this paper, pointed out to us the relevant lines of research in V-polytope theory .

References