# Find pairs of linearly associated linear combinations

I am trying to figure out if the following problem can be formulated using linear or quadratic programming: consider a set of $$n$$ normalized vectors $$V = \{V_1,..,V_n\}$$ with $$V_i \in \mathbb{R}^d$$. The goal is to find (sparse) pair(s) of linear combinations with $$a_1V_i + .. + a_lV_l$$ and $$b_1V_j + .. + b_mV_m$$ such that

1. the linear combinations in each pair are linearly associated/correlated.
2. the vectors in the first linear combination do not occur in the second linear combination (what I tried to indicate by using $$i, l$$ and $$j, m$$ when numbering the vectors in the aforementioned linear combinations. Sorry if this is weird use of notation.)
3. $$l + m < n$$ (or $$l < n$$ and $$m < n$$), i.e. the linear combinations are sparse/not all vectors in $$V$$ participate

The values $$a_1,..,a_l$$ and $$b_1,..,b_m$$ are coefficients/weights with $$a_i, b_i \in [-1,1]$$.

My attempt at modeling this problem is to formulate it as an optimization problem and set $$a_1V_1 + .. + a_nV_n + r_1 = b_1V_1 + .. + b_nV_n + r_2$$, which can be encoded as $$d$$ linear equality constraints (one for each dimension). Here, $$r_1, r_2 \in \mathbb{R}^d$$ are vectors that serve as slack variables (i.e. error/residual terms for when the values in the linear combinations of the vectors do not match exactly).

The objective then becomes the minimization of $$\sum_{i=1}^d (r_1 + r_2)$$. Since the objective and constraints are linear in this case, I can formulate this as a linear programming problem. For obtaining sparse combinations, I can add a regularization term. However, modeling the fact that one vector cannot occur in both linear combinations requires me to introduce a binary variable that sets either $$a_i = 0$$ or $$b_i = 0$$. This turns the problem into a mixed-integer LP which works but makes it hard to scale to larger $$n$$.

I wonder if there's a way to reformulate it as an LP or QP? The problem seems to me close to regression (least absolute deviation for LP formulation, least squares for QP formulation) except that there is no obvious starting $$y$$.

• It's unclear what you mean by requirement 1. What you have actually encoded using the slack variables and objective is that the two sums should be close to each other (in 1-norm), which is not the same as "linearly associated/correlated". (If 10 times the first sum minus 27 times the second sum is zero, the two sums can be called "linearly associated".) Jan 5 '20 at 16:09
• Thank you for your reply. You're right, I forgot to mention that the vectors are normalized beforehand. This should fix the case where the sums are not close (in 1-norm) but are linearly associated, right? Would it also be possible to formulate it using the $L_2$ norm (i.e. like a least squares regression, which would make it a QP problem)? I don't yet see how I could transform the constraints to achieve this without making the constraints quadratic (if that makes sense). Sorry for the immediate follow up question, just excited that I got a response to the question so quickly. Jan 5 '20 at 21:23
• I'm still uncertain what you mean in the first list item "the linear combinations in each pair are linearly associated/correlated", and whether this is a constraint or a goal (objective). Jan 6 '20 at 22:25
• The linear association of the linear combinations ($a_1V_1+..+a_nV_n+r_1$ and $b_1V_1+..+b_nV_n+r_2$) is the goal. But I try to achieve this by setting the optimization objective to minimize the sum of the residual terms $r_1, r_2$ of each linear combinations. My reasoning is then that by minimizing these two values, the linear combinations it finds should be "close" to each other so as to maximize their linear association/correlation. My reason for using the $L_1$ norm is so that I could express it as a linear program. But I want to prevent it to pick the same vector in both linear combi... Jan 7 '20 at 12:44
• ...nations. So I don't want it to pick say $V_1$ to end up in both linear combinations (I'm sorry for being unclear in my notation here). I can achieve this by introducing a binary variable that, for every coefficient $a_i, b_i$, sets $a_i = 0$ if $b_i > 0$ or vice-versa. But this turns it into a mixed-integer LP, which makes the optimization slow. So I am wondering if (1) my current way of setting up the optimization makes sense given the goal of making the linear combinations linearly associated/correlated and (2) if I can express this as an LP (or QP, with least squares) instead of an MILP. Jan 7 '20 at 12:47

• Thank you for this explanation and for your patience with my initially unclear question. If I could ask one more thing about an LP proposal for this problem, what if the constraint $a_1V_1+..+a_nV_n + r_1 = b_1V_1+..+b_nV_n + r_2$ would change to just $a_1V_1+..+a_nV_n - r_1 = 0$ with $a_i \in [-1,1]$? Essentially, minimizing just $r_1$ and moving all $b_1V_1,..,b_nV_n$ to the lefthand side? Wouldn’t this achieve the goal in that the (linear combination of) vectors with negative coefficients would be close to the (linear combination of) vectors with positive coefficients while satisfying (2)? Jan 8 '20 at 19:56
• I meant that that original constraint $a_1V_1 + .. + a_nV_n + r_1 = b_1V_1 + .. + b_nV_n + r_2$ (of the form $LHS = RHS$) changes to $a_1V_1 + .. + a_nV_n - r = 0$ with $a_i \in [-1,1]$ and then whatever vectors have $a_i > 0$ will form the lefthand side (LHS) linear combination while the vectors with $a_i < 0$ will form the righthand side (RHS) linear combination. So basically the constraint changes from $LHS = RHS$ to $LHS - RHS = 0$ with a single residual vector $r$. Then any $V_i$ can also only occur once and the LHS lin.comb. and RHS lin.comb. will be linearly associated? Jan 9 '20 at 22:09
• The infeasibility result is perplexing. You might want to try fixing the $a$ and $b$ variables at some arbitrary values (leave the residuals unfixed) and then ask Gurobi to find an irreducible infeasible subset of constraints (i.e., tell you why it thinks the model is infeasible). Jan 12 '20 at 15:39