Linear Algebra - Matrix Vector (Multiplication)

About

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):

in terms of linear combinations
in terms of dot-products

Articles Related

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 <math>r \in \mathbb{R}</math> .

Algebraic properties

Let A be an R x C matrix:

For any C-vector v and any scalar <math>\alpha</math> ,

<MATH> A*( \alpha v) = \alpha ( A * v) </MATH>

For any C-vector u and 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)

<MATH> M * v_c = \sum_{c \in C} ( v[c]*(columnVector_c \text{ of } M )) </MATH>

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

R-vector

<MATH> v_r * M = \sum_{r \in R} ( v_r[r]*(rowVector_r \text{ of } M)) </MATH>

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

Others (???)

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

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:

<math>\begin{bmatrix}a & c \\ b & d \end{bmatrix} * \begin{bmatrix}x \\ y \end{bmatrix} = \begin{bmatrix}p \\ q \end{bmatrix}</math>

Solution:

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

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. <MATH>v = [\text{for each } r \in R: v[r] = (row_r \text{ of } M) * u]</MATH>

Example: <MATH> \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} </MATH>

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
Solving a triangular system
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]:

<MATH> \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] </MATH>

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

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]