I have a vector $v \in \mathbb{N}^k$ and a set of vectors $R \subset \mathbb{N}^k$, with $k \ll \left\vert R \right\vert $.

I would like to find a way to obtain all the possible bases of $\mathbb{N}^k$ taking $k$ elements from $R$.

The ultimate goal is to find a decomposition of $v$ over a subset $S = \left\{ r_1, r_2, \ldots, r_q\right\} \subset R $ that will minimize a given cost function $f$.

Unfortunately the search space is really large ($\left\vert R \right\vert > 10^5$ even for basic problems), so I cannot just try to brute force a solution.

Is there any algorithm or theorem related to my problem that I could exploit?


It has been pointed out that $\mathbb{N}^k$ is not actually a vector space. I guess that it would be more correct to frame the problem in $\mathbb{Z}^k$, although all the components of all the vectors in my problem must be non-negative. I guess that a more correct statement is that $v \in (\mathbb{Z^+} \cup \left\{0\right\})^k$.

I forgot to specify an important condition: all the vectors in $R$ are such that the sum of their components does not exceed a given constant $T$. In fact, $R$ is defined as

$R = \left\{r \in \mathbb{N}^k \mid \sum r_i \le T \right\}$

When I say "decomposition of $v$ ", I mean that I would like to find a set of vectors $S = \left\{r_1, r_2, \ldots, r_n\right\} \subset R \subset \mathbb{N}^k$ such that $v$ is a linear combination of the elements of $S$. I am also assuming that $ 0 \in \mathbb{N}$. In formula:

$v = \sum x_i \cdot r_i$

where $x_i \in \mathbb{R}$ (truth be told, I am especially interested in the solutions where $x_i \in \mathbb{N}$, although those are simply better solutions than the non-integer ones).

The cost function is still under development and thus I don't have a precise formulation to share right now. Roughly speaking, it will be proportional to the cardinality of $S$, inversely proportional to the norm of each vector and inversely proportional to the number of non-zero components of each vector. Therefore, something essentially like this:

$ C(S) \propto \frac{\vert S \vert}{\sum \Vert s_i \Vert \cdot \sum V(s_i)}$

where $V \left(s\right)$ counts the non-zero components of $s$.

  • 1
    $\begingroup$ I think the total number of possible bases in R can be as large as the number of possible combinations of k elements out of | R |. If | R | is very big, just the size of the output (no matter how efficient the algorithm is) will be huge, and I'm not sure you can get below that... If there is a lot of collinearity in R it can be better I guess (to the point there could be not a single base in R). $\endgroup$ – jdehesa Jun 8 '17 at 16:11
  • $\begingroup$ @jdehesa : Unfortunately I think the same. For a small-scale problem, $R$ has 69 elements, which leads to 864501 combinations, 602400 of which are bases of the vector space. $\endgroup$ – Michele Ippolito Jun 9 '17 at 7:16
  • $\begingroup$ What's the precise definition of a basis? Is it that every element of $\mathbb{N}^k$ can be expressed as a linear combination of $r_1,\dots,r_n$, using coefficients in $\mathbb{N}$, i.e., every $x \in \mathbb{N}^k$ can be expressed as $x= \sum_i c_i r_i$ for some $c_1,\dots,c_n \in \mathbb{N}$? Or do you allow $c_1,\dots,c_n \in \mathbb{R}$? Does it need to be a basis? If $S$ weren't a basis, but you could still express $v$ as a linear combination of elements of $S$, would that be good enough? $\endgroup$ – D.W. Jun 9 '17 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.