Linear Algebra - Matrix Vector (Multiplication)

There is two ways to multiply a matrix by a vector:

• matrix vector
• or vector matrix

For each of these multiplication, two equivalent implementations (definitions):

Definition

Ordinary

“Ordinary” Definition of Matrix-Vector Multiplication: If M is an R x C matrix and u is a C-vector then M * u is the R-vector v such that, for each $r \in \mathbb{R}$ .

$$v[r] = \sum_{k \in C} (M[r,c]u[c])$$

Algebraic properties

Let A be an R x C matrix:

• For any C-vector v and any scalar $\alpha$ ,

$$A*( \alpha v) = \alpha ( A * v)$$

• For any C-vector u and v:

$$A*( u + v) = A * u + A * v$$

Type

Linear Combination

Linear Combination definitions for a matrix-vector multiplication with a matrix M (RxC).

If the vector is a:

• C-vector (If v is not a C-vector then error)

$$M * v_c = \sum_{c \in C} ( v[c]*(columnVector_c \text{ of } M ))$$

$$\begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [7,0,4] = 7 * [1,10] + 0 * [2,20] + 4 * [3,30]$$

• R-vector

$$v_r * M = \sum_{r \in R} ( v_r[r]*(rowVector_r \text{ of } M))$$

$$[7,4] * \begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} = 7 * [1,2,3] + 4 * [10,20,30]$$

• Others (???)

$$\begin{pmatrix} 1 & 2 & 3 \\ 10 & 20 & 30 \end{pmatrix} * [1,0.5,2] = \begin{pmatrix} 8 \\ 75 \end{pmatrix}$$

Application

Fundamental Computational Problem: Solving a linear matrix-vector equation

• input: an R x C matrix A and an R-vector b
• output: the C-vector x such that A * x = b

Problem:

• Simple formula to solve:

$\begin{bmatrix}a & c \\ b & d \end{bmatrix} * \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}p \\ q \end{bmatrix}$

• Solution:

$\text{if } ad \neq bc: x = \frac{\displaystyle dp - cq}{\displaystyle ad - bc} \text{ and } y = \frac{\displaystyle aq - bp}{\displaystyle ad - bc}$

A algorithm for solving a matrix-vector equation can be use to solve a vector-matrix equation, using transpose.

Dot Product

The Dot Product Definition of matrix-vector multiplication is the multiplication of two vectors applied in batch to the row of the matrix.

Let M be an R x C matrix, M * u is the R-vector v such that v[r] is the dot-product of row r of M with u. $$v = [\text{for each } r \in R: v[r] = (row_r \text{ of } M) * u]$$

Example: $$\begin{array}{rcl} \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ 10 & 0 \end{bmatrix} * [3,-1] & = & [ [1, 2].[3,-1], [3, 4].[3,-1], [10, 0].[3,-1] ] \\ & = & [ 1,5,30 ] \end{array}$$

Applications of dot-product

• Downsampling: Each pixel of the low-res image corresponds to a little grid of pixels of the high-res image. The intensity value of a low-res pixel is the average of the intensity values of the corresponding high-res pixels. Averaging can be expressed as dot-product. We want to compute a dot-product for each low-res pixel. Can be expressed as matrix-vector multiplication.
• blurring: To blur a face, replace each pixel in face with average of pixel intensities in its neighborhood. Average can be expressed as dot-product. By dot-product definition of matrix-vector multiplication, can express this image transformation as a matrix-vector product. Gaussian blur: a kind of weighted average
• Audio search: Lots of dot-products, Represent as a matrix-vector product, One row per dot-product. To search for [0,1,-1] in in [0, 0,−1, 2, 3,−1, 0, 1,−1,−1]:

$$\begin{bmatrix} \begin{array}{rrr} 0 & 0 & -1 \\ 0 & -1 & 2 \\ -1 & 2 & 3 \\ 2 & 3 & -1 \\ 3 & -1 & 0 \\ -1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & -1 & -1 \end{array} \end{bmatrix} * [0,1,-1]$$

Computation

To compute matrix-vector or vector-matrix product, we could use dot-product or linear-combinations definition. However, using those definitions, it’s not easy to exploit sparsity in the matrix.

• Without using sparsity

$$\text{for i in R:} \\ v[i] := \sum_{j \in C} M[i,j]u[j]$$

• Using sparsity in the matrix
initialize v to zero vector
for each pair (i , j) in sparse representation,
v[i] = v[i] + M[i,j] u[j]