2
$\begingroup$

Given a matrix $\color{red}{\mathbf A} \in \mathbb{Z}_{\ge 0}^{m \times n}$, find the row vector $\color{red}{\mathbf v} \in \mathbb{R}_{>0}^{1 \times m}$ such that the elements of $\color{red}{\mathbf{vA}}$ are equal to one another (or as close as possible).

Usually, $m > n$, but in rare scenarios, $m < n$.


Motivation

The vector $\color{red}{\mathbf v}$ is used to give weights to a set of equations which are minimized in a machine learning context. Each equation contains a varying number of predictors, which are represented in the matrix $\color{red}{\mathbf A}$; the columns are the different predictors and the rows are the minimized equations. To ensure that each predictor has approximately the same weight in the minimization routine, the equations are multiplied by the vector $\color{red}{\mathbf v}$.

$\color{red}{\mathbf v} > 0$ since each equation should be included in the minimization.

The solution needs to be programmable given the large size of $\color{red}{\mathbf A}$ (e.g., $m > 100$ and $n > 10$).


Example

$$\color{red}{\mathbf A}=\begin{bmatrix}0&4&2\\1&0&1\\2&2&0\\1&1&1 \end{bmatrix}$$

By inspection, $\color{red}{\mathbf v}=\begin{bmatrix}1&4&1&1\end{bmatrix}$ so that $\color{red}{\mathbf{vA}} = \begin{bmatrix}7&7&7\end{bmatrix}$.

Another solution is $\color{red}{\mathbf v}=\begin{bmatrix}0.5&2&1&1\end{bmatrix}$ so that $\color{red}{\mathbf{vA}}= \begin{bmatrix}5&5&5\end{bmatrix}$.

Any solution is acceptable as long as $\color{red}{\mathbf v} > 0$. (The elements of $\color{red}{\mathbf{vA}}$ do not have to be an integer).


Solution attempt

I am not super familiar with linear algebra, so the only solution I can think of is to iteratively search for $\color{red}{\mathbf v}$ using optimization.

The mean squared error between every element pair of $\color{red}{\mathbf{vA}}$ is the objective function. In our example:

$$MSE=\frac {(\mathbf{vA}_1 - \mathbf{vA}_2)^2 + (\mathbf{vA}_1 - \mathbf{vA}_3)^2 + (\mathbf{vA}_2 - \mathbf{vA}_3)^2}{3}$$

Find the vector $\color{red}{\mathbf v}$ that minimizes the $MSE$ (and whose elements $> 0$).

However, the solution needs to be as fast as possible, so I hope that an analytical solution exists, or at least a very fast iterative solution.

$\endgroup$
6
  • 2
    $\begingroup$ In the most recent edit, this error is minimized when $v$ is the vector of all zeros $\endgroup$
    – whpowell96
    May 24, 2023 at 21:47
  • $\begingroup$ @whpowell96, I've included the "non-null" clause in my question as I also realized that the vector $\mathbf{v}=\mathbf{0}$ is a solution, but which I am not interested in. $\endgroup$
    – Florent H
    May 24, 2023 at 21:53
  • $\begingroup$ Final form found, +1 ;) $\endgroup$
    – Piita
    May 24, 2023 at 22:40
  • $\begingroup$ Thank you for the help! =) $\endgroup$
    – Florent H
    May 24, 2023 at 22:42
  • $\begingroup$ What is $k$? Is it just an arbitrary integer? $\endgroup$
    – ConMan
    May 24, 2023 at 23:47

4 Answers 4

2
$\begingroup$

We want $Av \approx k[1,1,...,1]^T$. This is a typical least squares problem and the solution $v$ which minimizes $||Av - k[1,1,1,\dots,1]^T||_2$ is $v = k(A^TA)^{-1}A^T[1,1,\dots,1]^T$.

$\endgroup$
6
  • $\begingroup$ How would you do least squares with the constraint that $v > 0$? Perhaps something along the lines of "non-negative least squares"? $\endgroup$
    – Florent H
    May 25, 2023 at 16:13
  • $\begingroup$ Yes you are correct. Non-negative least squares is the way to go if you want $v > 0$ unless your loss function or objective function is not least squares. $\endgroup$
    – Balaji sb
    May 26, 2023 at 3:07
  • $\begingroup$ Isn't $k$ a decision variable as well? $\endgroup$ May 26, 2023 at 9:15
  • 1
    $\begingroup$ Non-negative least squares has the constraint that $\mathbf {v} \ge 0$; however, I don't want any zeros in $\mathbf v$. I found that doing a least squares fit with a non-zero lower bound using this SciPy implementation in Python was my best solution. $\endgroup$
    – Florent H
    May 26, 2023 at 15:53
  • 1
    $\begingroup$ If $v_i=0$ then choose $v_i$ as a very small positive number. It wont affect error that much. Anyway if you have found a solution to your problem then good luck. $\endgroup$
    – Balaji sb
    May 26, 2023 at 23:10
1
$\begingroup$

Augmented Matrix Solution
$\mathbf{v}A$ will produce something of the form: $$\mathbf{v}A = \begin{bmatrix}\mathbf{v}_{1} \cdot A_{11} + \mathbf{v}_{2} \cdot A_{21} + ... & \mathbf{v}_{1} \cdot A_{12} + \mathbf{v}_{2} \cdot A_{22} + ... & \mathbf{v}_{1} \cdot A_{13} + \mathbf{v}_{2} \cdot A_{23} + ...\end{bmatrix}$$ You can then produce an augmented matrix which follows the transpose of $A$: $$\left[\begin{array}{ccc|c} A_{11} & A_{21} & \dots & x \\ A_{12} & A_{22} & \dots & x \\ \vdots & \vdots & \ddots & \vdots \end{array}\right]$$ The augmented matrix is a convenient way of representing a set of simultaneous equations. Each column represents the coefficient of an element in $\mathbf{v}$. The first column corresponds to $\mathbf{v}_{1}$, the second to $\mathbf{v}_{2}$, etc.

You can then add or subtract rows from each other, provided that you also preserve whatever action you take on the right hand side. Or, you can multiply a whole row by some number, as long as you treat the right hand side the same.

Taking the example matrix $A$: $$A = \left[\begin{array}{ccc} 0 & 4 & 2 \\ 1 & 0 & 1 \\ 2 & 2 & 0 \\ \end{array}\right]$$

First transpose and augment: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 4 & 0 & 2 & x \\ 2 & 1 & 0 & x \\ \end{array}\right]$$

Let the $i^{th}$ row be represented as $R_i$, then subtract $R_1$ from $R_3$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 4 & 0 & 2 & x \\ 2 & 0 & -2 & 0 \\ \end{array}\right]$$

Add $R_3$ to $R_2$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 6 & 0 & 0 & x \\ 2 & 0 & -2 & 0 \\ \end{array}\right]$$

Take $\frac{R_2}{3}$ from $R_3$: $$\left[\begin{array}{ccc|c} 0 & 1 & 2 & x \\ 6 & 0 & 0 & x \\ 0 & 0 & -2 & -\frac{x}{3} \\ \end{array}\right]$$

Add $R_3$ to $R_1$: $$\left[\begin{array}{ccc|c} 0 & 1 & 0 & \frac{2x}{3} \\ 6 & 0 & 0 & x \\ 0 & 0 & -2 & -\frac{x}{3} \\ \end{array}\right]$$

Now you have a solution for any $x$: $$\left.\begin{array}{ccc} \mathbf{v}_1 = \frac{x}{6} & \mathbf{v}_2 = \frac{2x}{3} & \mathbf{v}_3 = \frac{x}{6} \end{array}\right.$$

It should be mentioned that a matrix with dimensions $m \times n$ where $n > m$ may have many solutions, since this is effectively asking for more elements in $\mathbf{v}$ than are required. In those cases, you can make $n-m$ of $\mathbf{v}$'s elements equal to zero and reduce the problem to a $m \times m$ square matrix.
This may not produce every solution. For instance it does not produce the $\mathbf{v} = \begin{bmatrix}0.5 & 2 & 1 & 1\end{bmatrix}$ result, as you can see in the above working.

In Coding Applications
If you are programming, you can perform this iteratively without as much regard for using numbers that play well with mental arithmetic. It would follow some process like:

  • Use some multiple of the first row to make one of the elements of the second row become zero
  • Use some combination of the first and second rows to make two of the elements of the third row become zero
  • Continue until you have a row with only one non-zero element
  • Use that row to make all of the other elements in the same column become zero
  • Now you should have a new row with only one non-zero element
  • Continue until you have only one non-zero element in each column

I'm afraid I can't offer a fastest algorithm, but this is at least a starting point.

$\endgroup$
2
  • $\begingroup$ Ah, I see that you have updated your question since I started writing this answer! I will try to correct it. $\endgroup$ May 24, 2023 at 23:28
  • $\begingroup$ Sorry about that! I needed to clarify things. If I'm not mistaken, your solution as it stands now does not consider that each element of $\mathbf v$ must be greater $0$. $\endgroup$
    – Florent H
    May 25, 2023 at 0:53
0
$\begingroup$

If you are solving with computer, you can use for example QR decomposition:

QR Decomposition

A rectangular matrix $\mathbf{A}\in\mathbb{R}^{m\times n}$ with $m\geq n$ can be decomposed into product of orthonormal matrix $\mathbf{Q}$ and upper triangle matrix $\mathbf{R}$:

$$ \mathbf{A} = \begin{bmatrix} \mathbf{Q}_{1} & \mathbf{Q}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} $$

Solving the Problem

$\mathbf{Q}$ is full rank so any arbitrary row vector $\mathbf{v}$ can be represented as: $\mathbf{v}=\mathbf{u}\mathbf{Q}^{T}$. We can then convert the initial problem as the following:

$$ \begin{aligned} \mathbf{v}\mathbf{A} &= \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1}^{T} \\ \mathbf{Q}_{2}^{T} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1} & \mathbf{Q}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{R} \\ \mathbf{0} \end{bmatrix} \\ &= \mathbf{u}_{1}\mathbf{R} \end{aligned} $$

To obtain $\mathbf{u}_{1}$:

$$ \mathbf{u}_{1} = \alpha\cdot \begin{bmatrix} 1,...,1 \end{bmatrix} \mathbf{R}^{-1} $$

Then your vector $\mathbf{v}$ is simply:

$$ \mathbf{v} = \begin{bmatrix} \mathbf{u}_{1} & \mathbf{u}_{2} \end{bmatrix} \begin{bmatrix} \mathbf{Q}_{1}^{T} \\ \mathbf{Q}_{2}^{T} \end{bmatrix} $$

with $\mathbf{v}_{2}$ arbitrary vector

$\endgroup$
2
0
$\begingroup$

Taking the transpose of $v A$ produces the vector $y$, where

$ y = A^T v^T $

Let $B = A^T, x = v^T $

We want $y$ to be along $ u = [1, 1, \dots, 1]^T $

That is $ y = k [1, 1, \dots, 1]^T $

Thus, we now have to solve the equation

$ B x - k u = 0 $

Define the augmented matrix

$ C = [B | - u ] $ and $ z = [ x ; k ] $

And find the solution of

$ C z = 0 $

For example, using your matrix, we have

$ C = \begin{bmatrix} 0 && 1 && 2 && 1 && -1 \\ 4 && 0 && 2 && 1 && - 1 \\ 2 && 1 && 0 && 1 && -1 \end{bmatrix} $

The null space (the solution of $C z = 0 $ ) is

$ z = t \begin{bmatrix} -1 \\ -4 \\ -1 \\ 6 \\ 0 \end{bmatrix} + s \begin{bmatrix} 1 \\ 4 \\ 1 \\ 0 \\ 6 \end{bmatrix} $

The solution of $[1, 4, 1, 1]$ is obtained by setting $ s = \dfrac{7}{6}, t = \dfrac{1}{6} $. This is one solution corresponding to $k = 7$

By setting $ s = \dfrac{5}{6}, t = \dfrac{1}{3}$, we obtain the solution $[0.5, 2, 0.5, 2] $ as one of possible solution corresponding to $k = 5 $

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .