Suboptimal Solution for a combinatorial problem

Question

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.

Answer 1

Mixed-integer quadratic programming

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.

Answer 2

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.