Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2}$. This matrix $X$ is generated by selecting only $s$ different rows from a matrix $B$ of dimension $n\times s$. At the end, we are going to choose one matrix $X$ that generates the least cost $f(X)$ within all possible $n\choose s$ submatrices of B. And so, this is a combinatorial problem that becomes complicated mostly when $n$ is big.

So my question is can we find a suboptimal solution without going through all possible $n\choose s$ submatrices and what kind of algorithm that I can apply to find such solution.

My second question is can we apply a feature selection algorithm to find a suboptimal solution for a combinatorial problem.

• I imagine that you can choose the rows with order, so it's actually $n^{\underline{s}}$ submatrices. Mar 5, 2014 at 21:45
• Are you allowed to use the same row twice? If so, then since $\|\hat{X}-X\|_2^2$ is just the sum of squares of all entries, this reduces to $s$ separate problems which can be solved in linear time by trying all the rows. When all rows in $\hat{X}$ are the same, you can even handle the constraint of choosing distinct rows, or even ordered rows. Mar 5, 2014 at 22:17
• If the rows are ordered, this is still easy for general $\hat{X}$ using dynamic programming. Mar 5, 2014 at 22:18
• @YuvalFilmus you are thinking of the Frobenius norm. The 2-norm is $\sup_{||v||_2=1} ||Xv||_2$. It is the largest sinular value, whereas the frobenius is the RMS of all the singular values Mar 5, 2014 at 22:19
• Do you want to find a good solution, or do you really just want exactly what you're asking for: a solution that is worse than the best solution? Mar 6, 2014 at 6:50

Given your updated question, this can be formulated as a mixed-integer quadratic programming problem.

Let $y_1,\dots,y_n$ be $n$ zero-or-one integer variables, subject to the constraint $y_1+\dots+y_n=s$, with the intent that if $y_i=1$ then we are selecting the $i$th row from $B$. Then for each $i,j$, the entry $(\hat{X}-X)_{i,j}$ can be expressed as a linear function of $y_1,\dots,y_n$. We are asking to minimize the objective function $\sum_i,j (\hat{X}-X)_{i,j}^2$, which is a quadratic objective function. Therefore, this can be expressed as a mixed-integer quadratic programming problem.

So, you could try throwing an off-the-shelf solver for mixed-integer quadratic programming at this and see how it does.

Closest vector problem

If everything in sight is an integer, I think this problem could also be approached as the problem of finding the closest point in a lattice to a given vector, the closest vector problem (CVP).

Consider the following lattice over a $n+s^2$-dimensional space. For each $i$, we have a basis vector of the form

$$(0,\dots,0,K,0,\dots,0,B_i,0,\dots,0),$$

where $K$ is a large constant (to be chosen later) and in the above, $K$ appears in the $i$th column, and $B_i$ is the $i$th row of $B$ and it appears starting in the $n+(i-1)s+1$th column. This gives us $n$ basis vectors, which form a basis for the lattice. Now we want to find the lattice point that is closest to the vector

$$(0,\dots,0,\hat{X}_1,\hat{X}_2,\dots,\hat{X}_s),$$

where the first $n$ columns of this vector are zero and $\hat{X}_i$ is the $i$th row of $\hat{X}$. If we choose $K$ appropriately, the closest lattice point has a good chance of being a sum of just $s$ of the basis vectors and thus forming a solution to this problem.

Now you could try to see if you can find any off-the-shelf CVP solvers, and see if they are effective at this problem. This is only going to work if everything is an integer: if you've got real numbers, I don't think this will work.

If you are willing to replace the induced $2$-norm with the Frobenius norm, then you can solve the problem column-by-column instead of all at once.

In a lot of practical situations I would expect the frobenius minimizer will be exactly the 2-norm minimizer, and is a common choice of norm to minimize in matrix completion problems.

edit: In a recent edit the original poster made it clear that what they are looking for is the frobenius norm, even though the notation $||\cdot||_2$ is traditionally used for the induced 2-norm. (the edit makes the problem much less interesting). Since the rest of this post is about justifying the Frobenius norm as an approximation to the induced 2-norm, it's basically irrelevant to the edited version of the question.

A little bit more on why the Frobenius norm could be a good approximation.

Since all norms are equivalent on a finite dimensional space, immediately we have $$c(s)||\hat{X} - X||_{Fro} \le ||\hat{X} - X||_2 \le C(s) ||\hat{X} - X||_{Fro},$$

so the Frobenius minimizer will be within a constant of the $2$-norm minimizer when the dimensions of the matrix are fixed. The issue, as usual, is that the constants $c(s), C(s)$ depend on the number of entries in the matrix and go to zero/blow up as $s$ becomes larger and larger.

However, there is a situation where the constants do not blow up and that is, roughly, when

1. you are dealing with a sequence of matrices $\hat{X}_s, B_s$ that are stably larger and larger approximations of some extremely high dimensional (or infinite dimensional) true matrices (operators) $\hat{X},B$, and
2. the very large or infinite "true" problem has a solution in the sense that there exists $X_{optimal}$ such that $\hat{X} - X_{optimal}$ is compact.

A little bit more on these conditions: 1) is the case if, for example

• your matrices are generated by incomplete sampling of data (eg., measurements from a scientific experiment where you could get better results by taking more data, or shopping data from a small subset of amazon's customers that are supposed to represent the customerbase as a whole), and you could get similar but bigger problems from the same distribution just taking more samples, or
• the size $s$ of your matrices comes from the level of discretication of a continuum problem like a partial differential equation.

Furthermore, 2) must always be the case if you reasonably expect a solution, since if there is no approximation that makes $\hat{X} - X$ compact, then by definition it has no finite rank approximation, so you can never come up with a good result to the real problem by solving limited data versions with $\hat{X}_s, B_s$ nomatter how big $s$ is.

Now, assuming that the compactness condition holds, the singular values $\sigma_1, \sigma_2, \dots$ of $\hat{X} - X_{optimal}$ are summable (and thus square summable), and so we have the explicit equivalence, $$||\hat{X} - X_{opt}||^2_{Fro} = \sum_{i=1}^{\infty} \sigma_i^2 = \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)\sigma_1^2 = \left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X} - X_{opt}||_2^2.$$

These constants are independent of $s$, and moreover the more compact the error, the faster the singular values decay, so the closer to 1 the equivalence constant is. Thus assuming that the matrices $\hat{X}_s, B_s$ come from stable sampling schemes or stable discretizations of $\hat{X},B$, we have the equivalence $$||\hat{X}_s - X_{s,opt}||^2_{Fro} \le \gamma_1\left(1 + \frac{\sum_{i=2}^{\infty} \sigma_i^2}{\sigma_1^2}\right)||\hat{X}_s - X_{s,opt}||_2^2 \le \gamma_2 ||\hat{X}_s - X_{s,opt}||^2_{Fro},$$ where $\gamma_1$, $\gamma_2$ come from the stability and coercivity constants of the sampling/discretization process.

So, since the assumptions above apply to a wide range of circumstances, replacing $2$-norm minimization with Frobenius norm minimization often makes sense in practical contexts.

• Actually the norm doesn't matter because I am looking to measure the error. In other words I am looking to see how $X$ is far from $\hat{X}$ Mar 6, 2014 at 6:51
• How you measure the error or "farness" is determined by the choice of norm. There are many different norms that might reasonably be chosen depending on the situation. Choosing the frobenius (elementwise) norm is saying that you think matrices are "close" if their elements are similar. Choosing an induced norm is saying that matrices are close if the way they act on vectors is similar. These are distinct but related concepts - the connection between the two is basically the main point of my post. Mar 6, 2014 at 17:14