# AN ALGORITHM FOR SINGULAR VALUE DECOMPOSITION OF MATRICES IN BLOCKS
Technical Report

Ávaro Francisco Huertas-Rosero

###### Abstract

Two methods to decompose block matrices analogous to Singular Matrix
Decomposition are proposed, one yielding the so called economy decomposition,
and other yielding the full decomposition. This method is devised to avoid
handling matrices bigger than the biggest blocks, so it is particularly
appropriate when a limitation on the size of matrices exists. The method is
tested on a document-term matrix (17780$\times$3204) divided in 4 blocks, the
upper-left corner being 215$\times$215.

##  1 Introduction

Singular Value Decomposition has proved to be useful in a wide range of
applications, where a linear relation is a suitable model for a big number of
variables. Its main strength is in its ability to abstract most of the
meaningfull relation in a much smaller subspace [7],[2],[6],[8].

Even though the calculations are very simple in essence, the method is at its
best when dealing with big dimension matrices of data, and the computational
resources to perform the calculations are often insufficient.

In this document I propose an algorithm that allows to deal with the matrix by
pieces, so it does not need to define big matrices or operate with them, but
only smaller blocks.

##  2 The usual algorithm

the usual algorithm to perform the decomposition is made in two steps: First,
a transformation is found that takes the matrix to bidiagonal form, and then,
the bidiagonal matrix is decomposed with a different procedure.

###  2.1 Householder transformations and bidiagonal matrices

The first step is carried by means as a certain class of symmetrical
orthogonal (or unitary) matrices called Householder transformations [3]. A
Householder transformation is defined by a unitary vector this way:

$H_{R}=1_{n\times n}-2(\hat{R})^{t}\hat{R}$ (1)

where $\hat{R}$ is an unitary vector of dimension (number of components) n,
and $1_{n\times n}$ is the identity with n rows and columns. It is easy to see
that the matrix that corresponds to this transformation is symmetric, which
means that it is not changed by transposition (changing rows by columns, and
vice versa). That impplies that it is its own inverse, e.i., that its square
is the identity matrix.

A householder operation can be found that, when multiplied by the left, turns
the all but one of the entries of the first column of a matrix into zero, but
preserving the sum of the squares of the entries of that column.

$\left(1_{n\times n}-2(\hat{R})^{t}\hat{R}\right)\begin{pmatrix}a\\\ d\\\ g\\\
k\end{pmatrix}=\begin{pmatrix}\sqrt{a^{2}+d^{2}+g^{2}+k^{2}}\\\ 0\\\ 0\\\
0\end{pmatrix}$ (2)

The unitary vector that defines the Householder transformation can be computed
as having one part proportional to the part that is to turn into zero. Being
an unitary vector, the proportionality factor can be best represented by some
unknown factor $X$ divided by the norm of that part of the vector, the square
root of the sum of the squares. In our example:

$\hat{R}=\left(\sqrt{1-X^{2}},\frac{Xd}{\sqrt{d^{2}+g^{2}+k^{2}}},\frac{Xg}{\sqrt{d^{2}+g^{2}+k^{2}}},\frac{Xk}{\sqrt{d^{2}+g^{2}+k^{2}}}k\right)$
(3)

Imposing the condition that it makes the required entries of the vector 0, the
unknown factor turns out to be:

$X=\frac{a+\sqrt{a^{2}+d^{2}+g^{2}+k^{2}}}{2\sqrt{a^{2}+d^{2}+g^{2}+k^{2}}}=\frac{a+Norm}{2Norm}$
(4)

We can express any matrix in block form, separating the first row and column,
in the same way as the Householder matrix. This latter has a very simple form:

$M=\begin{pmatrix}M_{0}&M_{row}\hat{V}_{row}\\\
M_{col}(\hat{V}_{col})^{t}&M_{block}\end{pmatrix}\\\
H_{M}=\frac{1}{N}\begin{pmatrix}M_{0}&M_{col}\hat{V}_{col}\\\
M_{col}(\hat{V}_{col})^{t}&-N\cdot
1_{(n-1)\times(n-1)}+(N-M_{0})\hat{V}^{t}\hat{V}\end{pmatrix}$ (5)

where $M_{0}$ is the first diagonal entry of the matrix, and the remaining of
the first row and first column are expressed by a norm and an unit vector,
$M_{row}\hat{V}_{row}$ and $M_{col}(\hat{V}_{col})^{t}$. N would be the norm
of the first column, that is $N=\sqrt{M_{0}^{2}+M_{col}^{2}}$

Multiplying the matrix $M$ by the Householder matrix by left, we get the
following result:

$H_{M}M=\frac{1}{N}\begin{pmatrix}N^{2}&-M_{col}M_{row}\hat{V}_{row}+M_{col}\hat{V}_{col}M_{block}\\\
0&M_{col}M_{row}(\hat{M}_{col})^{t}M_{row}-NM_{block}+(N-M_{0})(\hat{M}_{col})^{t}\hat{M}_{col}M_{block}\end{pmatrix}$
(6)

A Householder transformation applied on the right, can have the same effect of
annihilating all but one of the entries of the first row. But, if we try to
get a diagonal block matrix using two consecutive Householder transformation,
one on the left and one on the right, the second is going to turn the zero
entries produced by the first into other number, thus failing to produce a
block diagonal matrix.

We can, however, leave one nonzero element in the first column, and two
nonzero elements in the first row, using on the left a Householder
transformation that mixes the contents of the rows only from the second
element on:

Next we can focus on the right-bottom block of the matrix where the zero
elements have not yet been produced. The right and left Householder
transformation for that block can be computed, so it will be left with only
two nonzero elements in the first row and column. Then, the same is done for
the remaining block, and so on.

The number of steps necessary to bring the matrix to a bidiagonal form has
been $2n-1$, where $n$ is the lower dimension of the matrix. It is a very fast
step.

###  2.2 Iterative diagonalisation

To take the bidiagonal matrix to a diagonal form is not so easy, and cannot be
done in a fixed number of steps, but has to be an iterative process. The most
efficient method for this is the QR factorisation [4].

Starting from our upper bidiagonal matrix, the steps to be performed are:

  1. 1.

Construct the orthogonal transformation to bring the matrix to lower
triangular form, with Householder transformations like the ones we used in the
last part, but only applied by right.

  2. 2.

Apply the transformation by left as well. The result will be a matrix that is
not either upper or lower triangular, but has the values more concentrated on
the diagonal.

  3. 3.

Repeat the procedure.

All the steps are done with orthogonal transformation, and that ensures that
the singular values are preserved. In each step, besides, the square of every
diagonal element are increased with the squares of the other elements in the
row. That, together with the preservation of singular values, ensures
convergence.

###  2.3 getting the economy decomposition

The last procedure yields the two square unitary matrices, and the singular
values diagonal must be nonsquare. That means that a lot of memory is needed
for the unitaries, wich are huge matrices with double precision. A lighter
alternative is to compute the economy decomposition [1], wich give us just
slices of unitary matrices. The left one has as much rows as our matrix, but
only as much columns as the rank (number of nonzero singular values) of the
matrix. And the right one has as much columns as our matrix, but only as much
rows as the rank of the matrix.

$M=UDV^{t}\\\ U^{t}U=1_{rank}\hskip 56.9055ptV^{t}V=1_{rank}\\\ UU^{t}\neq
1_{rows}\hskip 28.45274ptVV^{t}\neq 1_{columns}$ (7)

To compute the economy decomposition, a lesser computational effort is needed.
Suppose that we have in our matrix more rows than columns, or that we took it
to that form by transposing it. Then, the symmetric matrix $A^{t}A$ will be
smaller in dimensions than A. We can use one of the usual algorithms to
diagonalise it, and get

$A^{t}A=VDV^{t}$ (8)

It is very easy to compute the inverse of square root of this matrix, all that
is necessary is to take inverses of square roots of the diagonal elements of
D. Then, we can express our matrix like this:

$A=A(A^{t}A)^{-1/2}(A^{t}A)^{+1/2}=\left(AVD^{-1/2}\right)D^{+1/2}V^{t}=UD^{+1/2}V^{t}$
(9)

It can be easily shown that $U=AVD^{-1/2}$ is a slice of a unitary matrix:

$U^{t}U=\left(D^{-1/2}V^{t}A^{t}\right)\left(AVD^{-1/2}\right)=D^{-1/2}V^{t}\left(A^{t}A\right)VD^{-1/2}=D^{-1/2}DD^{-1/2}=1$
(10)

If the square matrix $A^{t}A$ hapens to be singular, then $V$ is also a slice
of a square unitary, and $D$ is smaller, but allways invertible.

##  3 Frobenius norm and a better starting point

Latent Semantic Analysis, and other techniques, are based on the fact that
some big matrices can be accurately represented only by the bigger terms of
their spectral decomposition, that is, only the bigger singular values. The
usual convention to represent the diagonal matrix of singular values is in an
ordered form, from the biggest, in the first element, to the smallest.

The matrices are usually rather sparse, and with only some column and row
swaps, we can take the bigger elements up and to the left, so the matrix is
going to be closer to the desired form.

The singular value problem, as the eigenvalue problem, can be seen as a
maximisation of a certain value. The solution of the following problem gives
the left and right eigenvectors corresponding to the highest singular value:

$\displaystyle\text{LEFT: }maximise\ \langle\Psi|AA^{t}|\Psi\rangle$
$\displaystyle\ constrained\ by\ \langle\Psi||\Psi\rangle=1$ (11)
$\displaystyle\text{RIGHT: }maximise\ \langle\Phi|A^{t}A|\Phi\rangle$
$\displaystyle\ constrained\ by\ \langle\Phi||\Phi\rangle=1$ (12)

All along this work, the maximisation of the values in the upper left corner
of the matrix is going to be used to arrive near to the diagonal form. The
first thing that can be done, is just arranging the rows and columns to take
the higher values to the upper left corner of the matrix.

There is a well known result, that tells us that the Frobenius norm of a
matrix [5], that is, the trace of its square $\|A\|=\sqrt{Trace(A^{t}A)}$, is
the sum of the squares of the singular values, and is as well the sum of the
squares of all the elements of the matrix.

$Trace(A^{t}A)=\sum_{i}\left(\sum_{j}(A^{t})_{ij}A_{ji}\right)=\sum_{ij}(A_{ij})^{2}$
(13)

If we consider the other square matrix $AA^{t}$ the result is the same,
because in that case we just swap indexes $i$ and $j$. With the SVD
decomposition of the matrix, we only need to remember that a unitary matrix
does not affect the trace:

$\displaystyle Trace(A^{t}A)$
$\displaystyle=Trace\left(\left(V(D_{mn})^{t}U^{t}\right)(UD_{mn}V^{t})=Trace((D_{mn})^{t}D_{mn})\right)=\sum_{i}(\lambda_{ii})^{2}$
(14) $\displaystyle Trace(AA^{t})$
$\displaystyle=Trace\left(\left(U(D_{mn})^{t}V^{t}\right)(VD_{mn}U^{t})=Trace((D_{nm})^{t}D_{nm})\right)=\sum_{i}(\lambda_{ii})^{2}$
(15)

where $D_{mn}$ is a square $m\times n$ diagonal matrix with the singular
values.

A vector can be computed with the norms of each row, and the Cartesian norm of
this vector will be the frobenius norm of the matrix. The same can be done
with the columns. This two vectors can be used to sort the rows and columns of
the matrix to get the higher values in the upper left corner.

Afther that sorting, a definition of the blocks can be done, with some
criterion based on those row and column norms. The blocks can be defined, for
example, as to put a certain percentage of the whole frobenius norm in the
first column-block, and a certain percentage on the first row-block.

If only the higher singular values are needed, it is not necessary to
decompose the whole matrix, but instead two steps can be taken:

  1. 1.

Separate the subspace of the highest singular values from that of the lower
singular values

  2. 2.

Decompose only the block corresponding to the highest singular values

##  4 Partial SVD

In the proposed algorithm, the matrix is prepared so as to have more rows than
columns (transposed if necessary) and the columns are cut in such a way that a
fraction of the total square Frobenius norm is enclosed in the first column
block. The rows are separated in such a way to have square upper left block.

Then, each block can be considered separately, and that can require
considerably less computer resources.

##  5 A generalisation of Householder matrices for blocks

The first thing that can be done, is to generalise the concept of a
Householder transformations to any partition of the rows and columns of the
matrix in four blocks. The general form of such a transformation is the
following:

$H=\begin{pmatrix}1_{n\times n}-U(1_{m\times m}-\alpha)U^{t}&U\beta V^{t}\\\
V\beta U^{t}&1_{(N-n)\times(N-n)}V(1_{m\times
m}+\alpha)V^{t}\end{pmatrix}\hskip 28.45274pt$ (16)

where $U$ is a slice of a unitary matrix with $n$ rows and $m$ columns, and
$V$ is a slice of unitary matrix with $N-n$ rows and $m$ columns. This
transformation would be a $N\times N$ unitary matrix, to be multiplied by left
to a matrix with $N$ rows divided in two blocks with $n$ and $N-n$ rows, or by
right to a matrix with $N$ columns split in blocks with $n$ and $N-n$ columns.
$\alpha$ and $\beta$ are diagonal matrices of rank $m$ with the property
$\alpha^{2}+\beta^{2}=1_{m\times m}$

This matrix y symmetric and it is its own inverse, two of the properties of a
Householder transformation. A householder transformation shifts the sign of
only one vector, but this transformation can be shown to change the sign of
any vector that lies within a subspace. This subspace is defined by a set of
mutually orthogonal vectors, which can be arranged in a column or row block.
The matrix can be written also like this:

$H=1_{N\times N}-2\left(\begin{pmatrix}U\sqrt{\frac{1}{2}(1-\alpha)}\\\
-V\sqrt{\frac{1}{2}(1+\alpha)}\end{pmatrix}\begin{pmatrix}\sqrt{\frac{1}{2}(1-\alpha)}U^{t}&-\sqrt{\frac{1}{2}(1+\alpha)}V^{t}\end{pmatrix}\right)$
(17)

A transformation like this can be used, for example, to annihilate a block of
a matrix, just as in the usual SVD method. Here are the steps to annihilate a
nondiagonal block by multiplication by left:

  1. 1.

The two relevant blocks, the ones that are going to be transformed to
annihilate one of them, are decomposed. Full SVD is not necessary, a simple
decomposition Unitary-Symmetric will do.

$A_{ij}=U_{ij}S_{ij}\hskip
56.9055ptS_{ij}=\left((A_{ij})^{t}A_{ij})\right)^{1/2}\hskip
56.9055ptU_{ij}=A_{ij}S_{ij}^{-1}$ (18)

  2. 2.

The unitary factors of the two blocks are taken as the $U$ and $V$ matrices of
the Householder matrix

  3. 3.

If we take the first column of a 2x2 blocks matrix as the relevant blocks, the
action of the Householder matrix will give in the nondiagonal block:

$\begin{pmatrix}1-U(1-\alpha)U^{t}&U\beta V^{t}\\\ V\beta
U^{t}&1-V(1+\alpha)V^{t}\end{pmatrix}\begin{pmatrix}US_{11}&A_{12}\\\
VS_{21}&A_{22}\end{pmatrix}=\begin{pmatrix}\\#\\#\\#&\\#\\#\\#\\\ V(\beta
S_{11}-\alpha S_{21})&\\#\\#\\#\end{pmatrix}$ (19)

For this block to be zero, the parameters of the matrix must be:

$\alpha=(1_{m\times m}+S_{21}(S_{11})^{2}S_{21})^{-1/2}\hskip
56.9055pt\beta=(1_{m\times m}-\alpha^{2})^{1/2}$ (20)

There is another way of doing it as well, wich will probably take more time,
but is based on a well known technique: the GSVD: Generalised Single Value
Decomposition. This is the simultaneous decomposition of two matrices:

$A_{11}=UCX^{t}\hskip 56.9055ptA_{21}=VSX^{t}$ (21)

where, in the economy representation, $U$ and $V$ are slices of unitary
matrices with the same dimensions than those of the other method. X is a
square matrix. The matrices $S$ and $C$ are square and diagonal, and fulfil
$C^{2}+S^{2}=1$. They can be used indeed as $\alpha$ and $\beta$ respectively
($C=\alpha,S=\beta$) in the Householder matrix.

With this kind of Householder transformations, we can perform a complete (not
economy) blockwise decomposition of a matrix, iterating the annihilation of
the two nondiagonal blocks as shown in the figure:

##  6 Blocks and the trace trick

To be able to perform the decomposition directly in the economy
representation, a version of the eigenvalue (spectral) decomposition is
needed. The formula shown for annihilating blocks only works multiplied by one
side, but it does not work to annihilate nondiagonal blocks acting on both
sides, as an equivalence transformation.

For a 2x2 number symmetric matrix, the problem of diagonalising it amounts to
finding a certain number $x$ that fullfills:

$\displaystyle UMU^{t}=$ $\displaystyle\begin{pmatrix}\sqrt{1-x^{2}}&x\\\
x&-\sqrt{1-x^{2}}\end{pmatrix}\begin{pmatrix}A&B\\\
B&C\end{pmatrix}\begin{pmatrix}\sqrt{1-x^{2}}&x\\\
x&-\sqrt{1-x^{2}}\end{pmatrix}=D$ (22) $\displaystyle D$
$\displaystyle=\begin{pmatrix}\frac{1}{2}(A+B)+\sqrt{\frac{1}{2}(A-B)^{2}+C^{2}}&0\\\
0&\frac{1}{2}(A+B)-\sqrt{{\frac{1}{2}(A-B)^{2}+C^{2}}}\end{pmatrix}$

The condition is better derived from the null elements of the matrix, and is:

$(1-x^{2})B+x\sqrt{1-x^{2}}A=x\sqrt{1-x^{2}}C+x^{2}B$ (23)

Defining $\alpha=(1-2x^{2})$ the condition becomes very simple, because
$\sqrt{1-\alpha^{2}}=2x\sqrt{1-x^{2}}$

$\alpha B=\frac{1}{2}\sqrt{1-\alpha^{2}}(A-C)$ (24)

The solution is easily found to be:

$x=\sqrt{\frac{\sqrt{(A-C)^{2}+4B^{2}}-(A-C)}{2\sqrt{(A-C)^{2}+4B^{2}}}}$ (25)

On the other hand, if the entries of the matrix are suitably sized blocks, the
condition is a lot more complicated. We can represent the unitary matrix as
being constructed with blocks $x$, $y$ and $z$ having the form shown above for
Householder matrices.

$\displaystyle UMU^{t}=$ $\displaystyle\begin{pmatrix}x&y\\\
y^{t}&z\end{pmatrix}\begin{pmatrix}A&B\\\
B&C\end{pmatrix}\begin{pmatrix}x&y\\\ y^{t}&z\end{pmatrix}$ (26)
$\displaystyle=\begin{pmatrix}xAx+yB^{t}x+xBy^{t}+yCy^{t}&xAy+yB^{t}y+xBz+yCz\\\
y^{t}Ax+zB^{t}x+y^{t}By^{t}+zCy^{t}&y^{t}Ay+zB^{t}y+zCz\end{pmatrix}$

The noncommutativity of the matrices does not allow for an easy solution as
that with numbers. Furthermore, to solve the condition for the nondiagonal
elements should not be possible, except in the 2x2 or 2x3 blocks case, because
that could be translated to solve analytically a general equation of order
higher than five. That, according to Abel’s theorem, is not possible.

But there is something we can do, and it is working with traces. We can either
maximise the trace of the first diagonal block, or minimise the trace of the
square of the nondiagonal block.

On the other hand, using slices of the unitary matrices, and their complement
(the slice that is lacking for the total unitary) we can build an unitary
matrix $S$ that allow us to isolate just a subspace to work on it, thus
reducing substantially the dimensionality of the problem.

$S=\begin{pmatrix}U_{1}&\bar{U}_{1}&0&0\\\ 0&0&U_{2}&\bar{U}_{2}\end{pmatrix}$
(27)

Note that if block $(A^{t}A)_{12}$ is full rank, then $U_{1}$ would be square
and there would not be a $\bar{U}_{1}$.

Applying this unitary transformation to the matrix we get:

$S^{t}(A^{t}A)S=\begin{pmatrix}(U_{1})^{t}(A^{t}A)_{11}U_{1}&(U_{1})^{t}(A^{t}A)_{12}\bar{U}_{1}&(U_{1})^{t}(A^{t}A)_{11}U_{2}&(U_{1})^{t}(A^{t}A)_{12}\bar{U}_{2}\\\
(\bar{U}_{1})^{t}(A^{t}A)_{21}U_{1}&(\bar{U}_{1})^{t}(A^{t}A)_{22}\bar{U}_{1}&(\bar{U}_{1})^{t}(A^{t}A)_{21}U_{2}&(\bar{U}_{1})^{t}(A^{t}A)_{22}\bar{U}_{2}\\\
(U_{2})^{t}(A^{t}A)_{11}U_{1}&(U_{2})^{t}(A^{t}A)_{12}\bar{U}_{1}&(U_{2})^{t}(A^{t}A)_{11}U_{2}&(U_{2})^{t}(A^{t}A)_{12}\bar{U}_{2}\\\
(\bar{U}_{2})^{t}(A^{t}A)_{21}U_{1}&(\bar{U}_{2})^{t}(A^{t}A)_{22}\bar{U}_{1}&(\bar{U}_{2})^{t}(A^{t}A)_{21}U_{2}&(\bar{U}_{2})^{t}(A^{t}A)_{22}\bar{U}_{2}\end{pmatrix}$
(28)

The trace of the first diagonal block can be recovered from this matrix as the
sum of the first and third diagonal blocks.

If $U_{1}$ and $U_{2}$ are chosen as the unitaries that take the nondiagonal
block $(A^{t}A)_{12}$ to diagonal form $D_{N}$, things are very simplified in
the above expression

$(U_{1})^{t}(A^{t}A)_{12}U_{2}=D_{N}$ (29)
$S^{t}(A^{t}A)S=\begin{pmatrix}(U_{1})^{t}(A^{t}A)_{11}U_{1}&(U_{1})^{t}(A^{t}A)_{11}\bar{U}_{1}&D_{N}&0\\\
(\bar{U}_{1})^{t}(A^{t}A)_{11}U_{1}&(\bar{U}_{1})^{t}(A^{t}A)_{11}\bar{U}_{1}&0&0\\\
D_{N}&0&(U_{2})^{t}(A^{t}A)_{22}U_{2}&(U_{2})^{t}(A^{t}A)_{22}\bar{U}_{2}\\\
0&0&(\bar{U}_{2})^{t}(A^{t}A)_{22}U_{2}&(\bar{U}_{2})^{t}(A^{t}A)_{22}\bar{U}_{2}\end{pmatrix}$
(30)

Now, a transformation should be chosen that maximises the trace of the two
first blocks. This is accomplished by a transformation that diagonalises the
reduced matrix $\tilde{M}$. The computation of such transformation does not
represent a big computational cost, because of the relatively small size of
this matrix.

$\begin{pmatrix}(\alpha_{1})^{t}&(\beta_{1})^{t}\\\
(\beta_{2})^{t}&(\alpha_{2})^{t}\end{pmatrix}\begin{pmatrix}\tilde{M}_{11}&D_{N}\\\
D_{N}&\tilde{M}_{22}\end{pmatrix}\begin{pmatrix}\alpha_{1}&\beta_{2}\\\
\beta_{1}&\alpha_{2}\end{pmatrix}=\begin{pmatrix}D_{1}&0\\\
0&D_{2}\end{pmatrix}$ (31)

where $\tilde{M}_{11}=(U_{1})^{t}M_{11}U_{1}$ and
$\tilde{M}_{22}=(U_{2})^{t}M_{22}U_{2}$.

The final form of the matrix will be:

$\tilde{U}^{t}S^{t}(A^{t}A)S\tilde{U}=\begin{pmatrix}D_{1}&W&0&X\\\
W^{t}&\bar{\tilde{M}}_{11}&Y&0\\\ 0&Y^{t}&D_{2}&Z\\\
X^{t}&0&Z^{t}&\bar{\tilde{M}}_{22}\end{pmatrix}$ (32)

Where:

$W=(\alpha_{1})^{t}(U_{1})^{t}(A^{t}A)_{11}\bar{U}_{1}\hskip
56.9055ptX=(\beta_{1})^{t}(U_{2})^{t}(A^{t}A)_{11}\bar{U}_{2}\\\
Y=(\beta_{2})^{t}(U_{1})^{t}(A^{t}A)_{11}\bar{U}_{1}\hskip
56.9055ptZ=(\alpha_{2})^{t}(U_{2})^{t}(A^{t}A)_{11}\bar{U}_{2}$ (33)

and

$\tilde{U}=\begin{pmatrix}\alpha_{1}&0&\beta_{2}&0\\\ 0&1&0&0\\\
\beta_{1}&0&\alpha_{2}&0\\\ 0&0&0&1\end{pmatrix}$ (34)

The trace of the two first blocks will now be bigger, because the highest
eigenvalues of the reduced matrix are concentrated in $D_{1}$.

This procedure can be iterated, and each time the trace of the first blocks
will be bigger.

$U_{total}=S\tilde{U}=\begin{pmatrix}U_{1}\alpha_{1}&\bar{U}_{1}&U_{1}\beta_{2}&0\\\
U_{2}\beta_{1}&0&U_{2}\alpha_{2}&\bar{U}_{2}\end{pmatrix}$ (35)

##  7 An algorithm for block-SVD

Then, an algorithm can is proposed for block-SVD of a big matrix:

  1. 1.

Make sure that there are more (or the same) rows as columns, or transpose
otherwise. This first steps are performed with the sparse csv triplet
representation.

  2. 2.

Compute the rows and columns euclidean norm

  3. 3.

Order rows and columns in descending norm order

  4. 4.

Choose a cutting point for the rows and columns. This can be made in several
ways. The one tried here is taking the point where at least 2/3 of the
frobenius norm is in the first column block, and cut the row blocks as to
yield a square first diagonal block.

  5. 5.

Create the blocks the appropriate size

  6. 6.

Create the Householder unitary matrix that annihilates block 12

  7. 7.

From that starting point, iterate the maximisation of the trace of block 11 of
the square matrix $A^{t}A$ until a certain tolerance

  8. 8.

Perform SVD of the first block

  9. 9.

This gives an approximation of the eigenvalue decomposition of $A^{t}A$.
Multiplying the initial matrix (by blocks) times the inverse of the square
root (also by blocks) the two-block relevant vertical slice of the economy
unitary left ($U$ in $UDV^{t}$matrix are obtained. The relevant slice of the
other unitary is the first vertical 2-block slice of the unitary obtained by
iteration ($V$)

##  8 Some results

A matrix of the occurrences of 3204 words in 17780 documents was used. The
procedure of cutting the blocks gave blocks with the following
characteristics:

BLOCK | ROWS | COLUMNS | DENSITY | SQUARE NORM | NORM PERCENTAGE
---|---|---|---|---|---
whole | 17780 | 3204 | 0.35% | 5125858 | 100%
11 | 215 | 215 | 21.14% | 3323694 | 64.84%
12 | 215 | 2989 | 3.73% | 444596 | 8.67%
21 | 17565 | 215 | 0.51% | 96345 | 1.88%
22 | 17565 | 2989 | 0.28% | 1261223 | 24.60%

It must be noted that the matrix was cut as to leave blocks 11 and 21 with a
little more than 2/3 of the square frobenius norm.

The blocks of the matrix $A^{t}A$ had the following characteristics:

BLOCK | ROWS | COLUMNS | DENSITY | TRACE* | PERCENTAGE
---|---|---|---|---|---
whole | 3204 | 3204 | 0.35% | 5125858 | 100%
11 | 215 | 215 | 100% | 3420039 | 66.72%
12 | 215 | 2989 | 3.73% | 543980 | 10.61%
22 | 2989 | 2989 | 0.28% | 1705819 | 33.28%

(*)The ”trace” of the nondiagonal block is not actually a trace, but the sum
of its singular values. The traces of the diagonal blocks must of course sum
up to the total trace, so their percentages sum up to 100%. The percentage for
the nondiagonal block is only computed to measure how non-block-diagonal the
matrix is.

The sum of the singular values of the nondiagonal block is going to be called
nondiagonality from now on.

To enhance convergence, in every iteration whose number is the square of an
integer, a transformation is included that tries to annihilate the block 12,
but is damped by $\frac{1}{n}$, being $n$ the number of the iteration. This is
accomplished by computing matrix $\alpha$ and $\beta$ as if the whole
nondiagonal block was divided by $n$.

The values of the traces for the first five iterations are shown in the
following table:

| BLOCK 11 | BLOCK 22 | BLOCK 12 | TIME (s)
---|---|---|---|---
0 | 3420039 | 1705819 | 543980 | -
1 | 3864177 | 1261681 | 144997 | 4.54
2 | 3886512 | 1239346 | 24666 | 105.68
3 | 3888110 | 1237748 | 6828 | 96.09
4 | 3888370 | 1237488 | 3838 | 105.11
5 | 3888479 | 1237378 | 2183 | 107.09
6 | 3888541 | 1237317 | 1781 | 103.88
7 | 3888584 | 1237274 | 1187 | 104.18
8 | 3888617 | 1237241 | 1143 | 105.69
9 | 3888644 | 1237214 | 822 | 103.51
10 | 3888666 | 1237192 | 831 | 103.91
.. | ……. | ……. | …….. | …..
21 | 3888828 | 1237030 | 295 | 103.47
22 | 3888836 | 1237021 | 269 | 102.47
23 | 3888844 | 1237014 | 240 | 102.94
24 | 3888850 | 1237008 | 211 | 102.77
25 | 3888855 | 1237003 | 175 | 102.58
26 | 3888859 | 1236999 | 158 | 101.95
27 | 3888863 | 1236995 | 143 | 101.70
28 | 3888866 | 1236992 | 122 | 101.78
29 | 3888869 | 1236989 | 103 | 101.61
30 | 3888871 | 1236987 | 91 | 101.87
31 | 3888872 | 1236986 | 75 | 101.56

The criterion used for convergence was that the ratio $\frac{Norm\ 12}{Norm\
11}$ became 1/10000 of its initial value (about 1.16). It can be seen that the
trace of the first block is allways increased, as expected, but the sum of
eigenvalues of the nondiagonal block oscillates after some iterations.

The availability of memory for MATLAB 6.5 does not allow to perform the
complete SVD decomposition of the matrix, but it is possible to compute the
singular values. The singular values contained in the first $215\times 215$
block then account for 75% of the square block of the matrix.

The first 215 obtained singular values had differences under 1e-10 with those
calculated by the usual algorithm, except for the lowest four.

##  9 Aknowledgements

This work was sponsored by the European Comission under the contract
FP6-027026 K-Space and Foundation for the Future of Colombia COLFUTURO. I
would also like to aknowledge the valuable guidance of professor C. J. van
Rijsbergen and useful advise from Mark Girolami in the developement of this
work.

## References

  * [1] E. Anderson, Bai, C. Bischof, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. ammarling, A. McKenney, and D. Sorensen.  LAPACK Users’ Guide, chapter Singular Value Decomposition, pages 19–23.  Society for Industrial Mathematics, 1999.
  * [2] David Gleich and Leonid Zhukov.  Svd based term suggestion and ranking system.  In ICDM ’04: Proceedings of the Fourth IEEE International Conference on Data Mining (ICDM’04), pages 391–394, Washington, DC, USA, 2004\. IEEE Computer Society.
  * [3] Gene H. Golub and Charles H. van Loan.  Matrix Computations, chapter 5, pages 209–226.  Johns Hopkins University Press, 1996.
  * [4] Roger A. Horn and Charles R. Johnston.  Matrix Analysis, chapter 2, pages 112–117.  Cambridge University Press, 1999.
  * [5] Roger A. Horn and Charles R. Johnston.  Matrix Analysis, chapter 5, pages 112–117.  Cambridge University Press, 1999.
  * [6] Thomas K. Landauer, Peter W. Foltz, and Darrell Laham.  An introduction to latent semantic analysis.  Discourse Processes, 25:259–284, 1998.  http://lsa.colorado.edu/papers/dp1.LSAintro.pdf.
  * [7] Juan C. Valle-Lisboa and Eduardo Mizraji.  The uncovering of hidden structures by latent semantic analysis.  Inf. Sci., 177(19):4122–4147, 2007.
  * [8] P. Wiemer-Hastings, K. Wiemer-Hastings, and A. Graesser.  How latent is latent semantic analysis?  In Proceedings of the 16th International Joint Congress on Artificial Intelligence, pages 932–937, San Francisco, 1999. Morgan Kaufmann.


# UniCat: Crafting a Stronger Fusion Baseline for Multimodal Re-Identification

Jennifer Crawford
Modern Intelligence
<EMAIL_ADDRESS>
&Haoli Yin
Modern Intelligence
<EMAIL_ADDRESS>
&Luke McDermott
Modern Intelligence
<EMAIL_ADDRESS>
&Daniel Cummings
Modern Intelligence
<EMAIL_ADDRESS>
###### Abstract

Multimodal Re-Identification (ReID) is a popular retrieval task that aims to
re-identify objects across diverse data streams, prompting many researchers to
integrate multiple modalities into a unified representation. While such fusion
promises a holistic view, our investigations shed light on potential pitfalls.
We uncover that prevailing late-fusion techniques often produce suboptimal
latent representations when compared to methods that train modalities in
isolation. We argue that this effect is largely due to the inadvertent
relaxation of the training objectives on individual modalities when using
fusion, what others have termed modality laziness. We present a nuanced point-
of-view that this relaxation can lead to certain modalities failing to fully
harness available task-relevant information, and yet, offers a protective veil
to noisy modalities, preventing them from overfitting to task-irrelevant data.
Our findings also show that unimodal concatenation (UniCat) and other late-
fusion ensembling of unimodal backbones, when paired with best-known training
techniques, exceed the current state-of-the-art performance across several
multimodal ReID benchmarks. By unveiling the double-edged sword of "modality
laziness", we motivate future research in balancing local modality strengths
with global representations.

##  1 Introduction

Multimodal representation learning has rapidly grown in popularity as deep
learning researchers are continually innovating new ways to combine different
channels of information simultaneously. Common tasks in this field revolve
around using text and images for input/output [1] or even using image-paired
data as a basis for learning a joint embedding across a wide variety of
modalities (e.g., text, audio, IMU, depth) [4]. However, an often overlooked
subfield is in the area of multimodal re-identification (ReID), where the
objective is to match instances of the same object across different sensor
sources and type (e.g., visible spectrum, infrared). In many cases, ReID
entails learning object representations from multiple views such as in
security or retail applications, where one might want to identify if an object
appearing in one camera’s field-of-view is the same object appearing in
another camera later in time. In this setting, each modality can have its
strengths and limitations. For instance, although a regular RGB image has
color information, it will be affected by illumination changes (e.g., daytime
vs. nighttime), whereas an infrared image might not.

Despite their ambitious goals, many recent fusion methods encounter
limitations. A notable challenge is modality laziness as described by Du et
al. [3]. In conventional late fusion techniques that employ shared loss
functions between modalities—such as vanilla late fusion through concatenating
or averaging representations, where the cross-entropy (CE) loss is determined
after fusion [17]—there is potential for individual modalities to contribute
less to the overall training classification accuracy. This concern is
especially evident in downstream retrieval tasks like ReID. Based on findings
by Peng et al. [12], one could infer that when modalities are trained
individually, the representation of a single modality will have a direct
influence on the loss function since it’s the sole contributor in that
setting.

Guided by these challenges, this study zeroes in on evaluating fusion
techniques, especially within the ReID context. While our lens is sharply
focused on ReID, the derived insights hold broader relevance, extending to a
vast spectrum of multimodal tasks that utilize late fusion techniques. Our
main contributions begin with creating a comprehensive evaluation of late
fusion techniques in the current multimodal ReID landscape, spotlighting their
inherent limitations from a modality laziness perspective. Next, we provide
empirical evidence establishing late-fusion unimodal ensembled models as a new
strong baseline, outperforming existing state-of-the-art methods in multimodal
ReID benchmarks. Finally, we discuss plausible explanations for this
surprising performance behavior in the context of unimodal model ablations and
future research directions for better understanding multimodal representation
learning and model design.

##  2 Preliminaries and Method

Multimodal representation learning focuses on the efficient and effective
compression of high-dimensional data, especially for downstream tasks like
ReID. For this purpose, convolutional neural networks (e.g., ResNet-50) and
Vision Transformers (ViTs) are typically employed as visual encoders [10].
Within this context, late fusion stands out as the predominant method for
integrating multiple data modalities. This approach is favored over the less-
common early fusion, which integrates multiple data modalities before
inputting them into a single model. Notably, early fusion can be sensitive to
pre-processing and lacks scalability [13]. The late fusion approach first
encodes each modality separately before combining their outputs, usually via
averaging or concatenation mechanisms. While late fusion does not allow for
cross-modal interactions, it is one of the most widespread fusion strategies
due to the intuition that the approach is able to leverage already existing
and carefully optimized architectures for the distinct modalities.

In object ReID, the task is to match objects across different data captures,
typically from disparate views or time instances. Multimodal ReID datasets are
given by $n$ object samples, where each sample consists of $M$ coincidental
images (corresponding to $M$ modalities) and an identifying label (ID): for
each sample we have $[(x_{1},x_{2},...,x_{M}),y]$ where
$x_{i}\in\mathbb{R}^{C\times H\times W}$ is the $i$-th modality image of the
object and $y\in\mathcal{D}$ denotes its ID. We consider multiple views of an
object to be different samples that share the same object ID. Of note, the IDs
we see during train-time do not overlap with those seen at inference. As such,
object ReID is often solved not by using the direct output of a classifier,
but by bringing different views of the same object together in the latent
space and push different objects away from each other. This is commonly done
by combining a cross-entropy loss with contrastive learning in the form of
triplet loss:

$\mathcal{L}(z)=\mathcal{L}_{\text{tri}}(z)+\lambda\mathcal{L}_{\text{CE}}(\tilde{y},y)$
(1)

where $\mathcal{L}_{\text{tri}}$ is a soft-margin triplet loss (further
defined in Appendix B) that uses the object embedding $z$ and
$\mathcal{L}_{\text{CE}}$ denotes a cross-entropy loss that uses the output of
a linear classifier, $\tilde{y}$. Here, $\lambda$ acts as a balancing
coefficient.

To establish a strong baseline for future multimodal ReID research and
investigate the impacts of fusion, we study three separate vanilla late-fusion
strategies: fusion by concatenation (Fusion-concat), fusion by averaging
(Fusion-avg), and post-training fusion by unimodal concatenation (UniCat).

More specifically, for each modality we train an unshared backbone, $f_{i}$
that produces a modality-specific embedding, $z_{i}$. These modality-specific
embeddings can then be combined into a multimodal representation:
$z_{\text{fuse}}=\Theta(z_{1},z_{2},...z_{M})$ where $\Theta$ is the chosen
fusion operator. The difference among the training strategies lies in whether
global or local loss functions are used. In Fusion-avg or Fusion-concat, we
use a global loss function that operates on the fused multimodal
representation, $z_{\text{fuse}}$:
$\mathcal{L}_{\text{fusion}}=\mathcal{L}(z_{\text{fuse}},\tilde{y}_{\text{fuse}})$.
In this case, the back-propagated gradients for each modality are entangled as
described in [12]. Conversely, in UniCat we train each modality encoder
independently with their own local loss function:
$\mathcal{L}_{\text{post}}=\sum_{i}^{M}\mathcal{L}(z_{i},\tilde{y}_{i})$ where
$i$ is summed over all modalities. Here, note that each modality’s loss is
fully disentangled from the others. In this case, fusion occurs only at
inference when we concatenate the modality-specific embeddings into the final
multimodal representation, $z_{\text{fuse}}$. For additional details on the
training strategies used, please see Appendix B.

##  3 Results

Figure 1: RGB, NIR, TIR
images from RGBNT100 [7].

We benchmark the described late-fusion strategies on three multimodal ReID
datasets. RGBNT100 [7] is a multimodal vehicle dataset consisting of
coincidental visible (RGB), near-infrared (NIR), and thermal-infrared (TIR)
images for 100 vehicles from multiple views as shown in Figure 1. RGBN300 is
an extension of RGBNT100 in which (RGB, NIR) pairs are provided for 300
vehicles. Lastly, RGBNT201 [18] is a multimodal person dataset that provides
(RGB, NIR, TIR) image triples for 201 different individuals. The key
benchmarks, mAP and Rank-1, are informed by the cumulative match curve (CMC)
[21]. Notably, mAP offers an overarching performance measure.

We compare our late-fusion baseline strategies with the previous state-of-the-
art multimodal ReID models (described in the Appendix A). In particular, we
test two of the most widely-used backbones found in other ReID models,
ResNet-50 and ViT-B.

In Table 1 we observe that RGBNT100/RGBN300 with UniCat and RGBNT201 with
Fusion-concat do strikingly better than the other best-known fusion
approaches, achieving state-of-the-art performance. We observe backbone choice
to have a more dramatic impact on RGBNT201 than RBGNT100/RGBN300. Since
RGBNT201 contains 2x fewer datapoints than RGBNT100, data-hungry ViTs may
struggle to learn with lack of inductive biases compared to CNNs [22].
Overall, we clearly observe fusion strategy as a leading factor on
representation quality.

Model Backbone RGBNT100 RGBN300 RGBNT201 mAP Rank-1 mAP Rank-1 mAP Rank-1
PFNET [18] ResNet-50 68.1† 94.1† - - 31.8 54.6 IEEE [15] ResNet-50 61.3† 87.8†
- - 46.42 47.13 HAMNet [7] ResNet-50 64.1 84.7 61.9 84.0 27.68∗ 26.32∗ CCNet
[19] ResNet-50 77.2 96.3 - - - - PHT [11] ViT-B 79.9 92.7 79.3 93.7 - -
Fusion-avg ResNet-50 75.3 $\pm$0.6 92.2 $\pm$0.9 74.9 $\pm$0.5 91.2 $\pm$0.6
57.6 $\pm$2.9 61.0 $\pm$3.0 Fusion-concat ResNet-50 75.1 $\pm$0.9 92.7
$\pm$0.6 74.7 $\pm$0.4 91.3 $\pm$0.2 63.0 $\pm$1.9 66.7 $\pm$3.1 UniCat
ResNet-50 79.4 $\pm$0.5 94.9 $\pm$0.8 76.7 $\pm$0.4 92.3 $\pm$0.4 38.1
$\pm$1.3 33.6 $\pm$1.7 Fusion-avg ViT-B 76.1 $\pm$0.3 90.1 $\pm$0.9 78.1
$\pm$0.1 91.4 $\pm$0.4 56.1 $\pm$2.2 54.9 $\pm$1.8 Fusion-concat ViT-B 75.9
$\pm$0.7 92.3 $\pm$0.4 77.4 $\pm$0.3 91.8 $\pm$0.3 61.7 $\pm$2.1 60.6 $\pm$1.2
UniCat ViT-B 81.3 $\pm$0.9 97.5 $\pm$0.3 80.2 $\pm$0.2 92.9 $\pm$0.4 57.6
$\pm$2.0 58.0 $\pm$1.8

Table 1: Comparison between current state-of-the-art multimodal ReID models
with our strong multimodal baselines. Metrics for our models were calcluated
by averaging performance across four random seeds. ${\dagger}$, $*$ indicates
the results were taken from [19] and [15], respectively.

To gain intuition for the dynamics at play, we further compare all of our
modality backbones on the task of unimodal ReID. That is, we use our trained
modality encoders from Table 1 and evaluate unimodal ReID performance on the
test sets. Because the multimodal embeddings in all fusion cases are simply
poolings of unimodal embeddings, multimodal ReID performance here is closely
tied to the corresponding unimodal ReID performance of the constituent
modalities. As shown in Table 2, for RGBNT100 we observe that all unimodal
ReID performance has been negatively affected by training with fusion.
Surprisingly, we also observe this to be the case in RGBNT201, with the
exception of one modality - NIR (see Table 3). We can consider this modality a
weak-link since when trained in isolation (UniCat) its performance is notably
lower than RGB/TIR. As multimodal ReID is most affected by the weakest-link,
we deduce that the performance gains of NIR in the case of Fusion-concat
outweighed the performance drops in RGB/TIR.

We suspect these effects are largely due to the impact and nuances of modality
laziness111For insight into the fundamental nature by which modality laziness
operates, see Appendix C for an experiment dealing with single-modality
ensembles.. To confirm that this underlies what we observe, as opposed to
overfitting as speculated by [14], we evaluate the embeddings of the RGBNT100
training set and find that they achieve a lower unimodal ReID performance in
the cases of training with fusion (Appendix D). The results shown by
RGBNT100/RGBN300 demonstrate the negative effects that modality laziness can
have - leading to underutilized unimodal features. Conversely, for datasets
such as RGBNT201 where noisy, less-reliable modalities exist, modality
laziness may offer a training relief by helping to prevent those modalities
from resorting to high-degrees of overfitting. This latter notion has also
been hypothesized by Liu et al. [8].

Model Backbone RGB NIR TIR mAP Rank-1 mAP Rank-1 mAP Rank-1 Fusion-avg
ResNet-50 48.6 $\pm$1.4 71.9 $\pm$0.9 40.4 $\pm$0.5 62.3 $\pm$1.3 41.1
$\pm$1.1 71.0 $\pm$2.3 Fusion-concat ResNet-50 44.7 $\pm$1.2 63.9 $\pm$2.8
27.3 $\pm$1.0 43.5 $\pm$1.1 36.9 $\pm$1.5 62.9 $\pm$1.3 UniCat ResNet-50 55.0
$\pm$0.8 77.2 $\pm$0.9 46.0 $\pm$1.1 67.3 $\pm$1.0 52.5 $\pm$0.4 82.5 $\pm$1.3
Fusion-avg ViT-B 51.7 $\pm$0.8 73.5 $\pm$0.9 41.8 $\pm$0.6 59.4 $\pm$2.7 31.0
$\pm$0.9 53.6 $\pm$2.8 Fusion-concat ViT-B 50.0 $\pm$4.1 70.8 $\pm$5.6 38.9
$\pm$2.5 60.7 $\pm$1.5 34.1 $\pm$1.6 61.6 $\pm$3.0 UniCat ViT-B 58.4 $\pm$0.83
80.2 $\pm$1.2 51.4 $\pm$0.8 71.5 $\pm$1.5 46.1 $\pm$2.5 76.0 $\pm$3.2

Table 2: RGBNT100 [7] Evaluation of unimodal ReID using the embeddings learned
from our multimodal late-fusion ReID baselines.

Model Backbone RGB NIR TIR mAP Rank-1 mAP Rank-1 mAP Rank-1 Fusion-avg
ResNet-50 21.4 $\pm$1.8 17.5 $\pm$3.0 14.8 $\pm$1.0 11.5 $\pm$0.6 33.0
$\pm$1.9 33.6 $\pm$3.5 Fusion-concat ResNet-50 16.7 $\pm$2.3 14.2 $\pm$2.8
18.9 $\pm$2.1 16.6 $\pm$2.8 28.5 $\pm$0.6 30.0 $\pm$1.5 UniCat ResNet-50 23.2
$\pm$2.0 18.34 $\pm$2.5 11.5 $\pm$0.6 7.4 $\pm$0.3 36.0 $\pm$0.3 36.9 $\pm$1.2
Fusion-avg ViT-B 28.1 $\pm$1.8 25.2 $\pm$1.6 20.5 $\pm$2.2 16.5 $\pm$3.0 27.6
$\pm$0.8 26.2 $\pm$1.1 Fusion-concat ViT-B 28.2 $\pm$2.7 25.8 $\pm$2.8 24.7
$\pm$1.5 23.7 $\pm$0.9 30.0 $\pm$0.8 29.0 $\pm$1.5 UniCat ViT-B 31.9 $\pm$0.8
29.6 $\pm$1.2 20.9 $\pm$1.1 16.8 $\pm$1.5 37.5 $\pm$1.3 36.2 $\pm$1.6

Table 3: RGBNT201 [18] Evaluation of unimodal ReID using the embeddings
learned from our multimodal late-fusion ReID baselines.

##  4 Discussion

Our results indicate that when different modalities are jointly optimized
(fusion training), they may not capture all available task-relevant
information, leading to potential underrepresentation. This is especially
pronounced in datasets like RGBNT100/RGBN300. But there’s a silver lining:
while certain modalities suffer, noisy ones may benefit since joint training
seems to act as a form of regularization for such modalities, preventing
overfitting to task-irrelevant data. Thus, a delicate equilibrium emerges in
multimodal ReID learning. We find that the UniCat approach using a ViT-B
backbone outperforms in both RGBNT100 and RGBN300. Here, each modality—RGB,
NIR, and TIR—benefits from the pressure of being trained in isolation.
Challenging views like those in [14] which focus on over-parameterization, our
results suggest that joint optimization’s nuances may limit modalities from
capturing complete task-relevant information, therein lying the negative
effects of modality laziness. Conversely, in certain scenarios, such as with
the RGBNT201 dataset, the utility of modality laziness emerges. Specifically,
the Fusion-concat method bolsters the performance of NIR—a notably weaker
modality. While NIR struggles when optimized individually, joint optimization
uplifts its performance. This could be attributed to modality laziness acting
as a shield against the modality’s inherent noise, resonating with the
observations made by [8]. This not only highlights the protective role of
modality laziness but also underscores its potential as a regularization
mechanism, especially for modalities with less task-relevant information.
Previous solutions to modality laziness ([3], [12]) do not consider the full
scope of the phenomenon.

Our findings show that while our simple baseline multimodal ReID models
outperform existing state-of-the-art, much research is still needed to inform
more holistic, nuanced multimodal frameworks. We encourage researchers in this
field to validate simple post-training fusion baselines like UniCat first in
their setting, before pursuing more complex fusion strategies. Lastly,
frameworks that are both model parameter efficient (e.g., a shared backbone
encoder) and data efficient are essential for future architecture scalability.

## References

  * [1] Cem Akkus, Luyang Chu, Vladana Djakovic, Steffen Jauch-Walser, Philipp Koch, Giacomo Loss, Christopher Marquardt, Marco Moldovan, Nadja Sauter, Maximilian Schneider, Rickmer Schulte, Karol Urbanczyk, Jann Goschenhofer, Christian Heumann, Rasmus Hvingelby, Daniel Schalk, and Matthias Aßenmacher.  Multimodal deep learning, 2023.
  * [2] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE conference on computer vision and pattern recognition, pages 248–255. Ieee, 2009.
  * [3] Chenzhuang Du, Jiaye Teng, Tingle Li, Yichen Liu, Tianyuan Yuan, Yue Wang, Yang Yuan, and Hang Zhao.  On uni-modal feature learning in supervised multi-modal learning, 2023\.
  * [4] Rohit Girdhar, Alaaeldin El-Nouby, Zhuang Liu, Mannat Singh, Kalyan Vasudev Alwala, Armand Joulin, and Ishan Misra.  Imagebind: One embedding space to bind them all, 2023.
  * [5] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Delving deep into rectifiers: Surpassing human-level performance on imagenet classification, 2015.
  * [6] Shuting He, Hao Luo, Pichao Wang, Fan Wang, Hao Li, and Wei Jiang.  Transreid: Transformer-based object re-identification.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), pages 15013–15022, October 2021.
  * [7] Hongchao Li, Chenglong Li, Xianpeng Zhu, Aihua Zheng, and Bin Luo.  Multi-Spectral Vehicle Re-Identification: A Challenge.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(07):11345–11353, April 2020.
  * [8] Kuan Liu, Yanen Li, Ning Xu, and Prem Natarajan.  Learn to combine modalities in multimodal deep learning, 2018.
  * [9] Hao Luo, Youzhi Gu, Xingyu Liao, Shenqi Lai, and Wei Jiang.  Bag of tricks and a strong baseline for deep person re-identification, 2019.
  * [10] Purvanshi Mehta.  Multimodal deep learning, 2020.
  * [11] Wenjie Pan, Linhan Huang, Jianbao Liang, Lan Hong, and Jianqing Zhu.  Progressively hybrid transformer for multi-modal vehicle re-identification.  Sensors, 23(9), 2023.
  * [12] Xiaokang Peng, Yake Wei, Andong Deng, Dong Wang, and Di Hu.  Balanced multimodal learning via on-the-fly gradient modulation, 2022\.
  * [13] Dhanesh Ramachandram and Graham W. Taylor.  Deep multimodal learning: A survey on recent advances and trends.  IEEE Signal Processing Magazine, 34(6):96–108, 2017.
  * [14] Weiyao Wang, Du Tran, and Matt Feiszli.  What makes training multi-modal classification networks hard?, 2020.
  * [15] Zi Wang, Chenglong Li, Aihua Zheng, Ran He, and Jin Tang.  Interact, embed, and enlarge: Boosting modality-specific representations for multi-modal person re-identification.  Proceedings of the AAAI Conference on Artificial Intelligence, 36(3):2633–2641, Jun. 2022.
  * [16] Hong Xuan, Abby Stylianou, Xiaotong Liu, and Robert Pless.  Hard negative examples are hard, but useful, 2021.
  * [17] Mang Ye, Jianbing Shen, Gaojie Lin, Tao Xiang, Ling Shao, and Steven C. H. Hoi.  Deep learning for person re-identification: A survey and outlook.  CoRR, abs/2001.04193, 2020.
  * [18] Aihua Zheng, Zi Wang, Zihan Chen, Chenglong Li, and Jin Tang.  Robust multi-modality person re-identification.  Proceedings of the AAAI Conference on Artificial Intelligence, 35:3529–3537, 05 2021.
  * [19] Aihua Zheng, Xianpeng Zhu, Zhiqi Ma, Chenglong Li, Jin Tang, and Jixin Ma.  Cross-directional consistency network with adaptive layer normalization for multi-spectral vehicle re-identification and a high-quality benchmark.  Information Fusion, 100:101901, 2023.
  * [20] L. Zheng, L. Shen, L. Tian, S. Wang, J. Wang, and Q. Tian.  Scalable person re-identification: A benchmark.  In 2015 IEEE International Conference on Computer Vision (ICCV), pages 1116–1124, Los Alamitos, CA, USA, dec 2015. IEEE Computer Society.
  * [21] Liang Zheng, Liyue Shen, Lu Tian, Shengjin Wang, Jingdong Wang, and Qi Tian.  Scalable person re-identification: A benchmark.  In Proceedings of the IEEE international conference on computer vision, pages 1116–1124, 2015.
  * [22] Haoran Zhu, Boyuan Chen, and Carter Yang.  Understanding why vit trains badly on small datasets: An intuitive perspective, 2023.

##  Appendix A Related Work

In current multimodal ReID literature, fusion approaches can be broadly
categorized into late and middle fusion. Late fusion entails processing each
modality independently and merging the representations in the final stages.
Middle fusion, a subtype of late fusion, involves interchanging features
between modalities to create an intricately fused representation upon which
subsequent tasks are executed. This nuanced approach in middle fusion allows
for a more integrated analysis of modalities compared to traditional late
fusion.

###  A.1 Late Fusion Approaches:

HAMNet [7]. The paper introduces HAMNet, a multi-stream convolutional network
(i.e. separate ResNet50 for each modality) tailored for multimodal vehicle
ReID. It employs multiple backbones to independently process each modality;
however, their method joins the features from each modality via a modified
pooling operation and uses a global loss function on the joint representation,
which suffers from modality laziness per our previous discussion.

CCNet [19]. CCNet, as described in the paper, is a multimodal vehicle ReID
model that employs a multi-stream architecture, with each branch dedicated to
processing individual modalities. This method mirrors the approach of UniCat
through its use of modality-specific cross entropies. However, CCNet differs
by incorporating global contrastive losses, which is suboptimal.

PHT [11]. The paper introduces the Progressively Hybrid Transformer (PHT) for
multimodal vehicle ReID. This method employs individual transformer branches
for each modality and integrates them at a singular depth, while utilizing the
Modal-specific Controller (MC) and Modal Information Embedding (MIE) for
modality adjustments. This design embodies late fusion, given the independent
modality processing and a singular fusion point using averaging. Notably, this
was the previous state-of-the-art method and is the first transformer-based
method to tackle the multimodal ReID problem. However, late fusion with
averaging prevents each modality from extracting the maximum amount of task-
relevant information per modality laziness.

###  A.2 Middle Fusion Approaches:

PFNET [18]. The Progressive Fusion Network (PFNet) for multimodal person ReID
follows a middle fusion approach, initially processing modalities separately
but later integrating them through intermediate and global stages. Despite its
middle fusion characteristics, the architecture predominantly relies on simple
concatenation of latent factors, which may not be optimally aligned for the
desired tasks. This suggests a potential need for a more constrained inter-
modality interaction and balance in learning effective representations.

IEEE [15]. The Interact, Embed and EnlargE (IEEE) method for multimodal person
ReID employs independent modality processing, followed by cross-modal
interactions and feature enhancements. This middle fusion strategy is evident
as it interchanges and integrates modality-specific features at intermediate
stages. However, its reliance on basic feature summation and late-stage
concatenation suggests further investigation into how to best balance the
trade-offs to alleviate modality laziness.

##  Appendix B Training Details

For training, we combine triplet loss $\mathcal{L}_{\text{tri}}$ [6] that
tries to increase class separability of the embeddings $z$ with a cross-
entropy loss $\mathcal{L_{\text{CE}}}$ that seeks to put the embeddings into
class-specific subspaces [9] (see eqn 1). Specifically, we use a modified
soft-margin triplet loss that includes hard-mining [16] to select the most
challenging positive and negative samples ($p$ and $n$) for a given anchor
($a$):

$\mathcal{L}_{\text{tri}}=\min_{n}\max_{p}\log\left(1+\exp\left(||a-p||_{2}-||a-n||_{2}+\alpha\right)\right)$
(2)

For the cross-entropy (CE) loss, class-wise output scores are found via a
linear classifier, and then compared against the ground truth. When combining
these losses in eqn 1 we set the balancing coefficient $\lambda$ to 1.

Images are resized to 128x256 for RGBNT100/RGBN300 and 256x128 for RGBNT201.
During training, images are augmented with random horizontal flipping,
padding, random cropping and random erasing [6]. We use many of the training
strategies suggested by [9], including a linear warmup strategy for the
learning rate and using BNNeck to normalize features before CE loss. For each
fusion strategy, we perform grid-search hyperparameter optimization across
three batch sizes ([64, 128, 256]) and three learning rates ([.008, .016,
.032]). We train for 120 and 200 epochs for ViT-B and ResNet-50 backbones,
respectively, used SGD with momentum 0.9 and a cosine learning rate decay. All
backbones are instantiated with Imagenet [2] pre-trained weights while the
linear classifier and bottleneck layers are instantiated via [5]. Similar to
[9], we choose cosine distance as our similarity metric for ReID.

##  Appendix C Effects of Fusion Strategies in Ensemble Learning

Model | RGBNT100 | Market1501
---|---|---
RGB | NIR | TIR
mAP | Rank-1 | mAP | Rank-1 | mAP | Rank-1 | mAP | Rank-1
Fusion avg | 57.7 | 79.1 | 48.6 | 67.7 | 48.6 | 76.9 | 87.6 | 94.9
Fusion-concat | 58.4 | 81.0 | 48.9 | 70.0 | 47.4 | 80.8 | 87.9 | 94.8
UniCat | 60.4 | 84.4 | 50.7 | 72.9 | 49.7 | 81.1 | 89.1 | 95.4
Table 4: Comparison of late-fusion implementations for a two-backbone (ViT-B)
unimodal ensemble learner.

Peng et al. [12] suggests that modality laziness occurs when some modalities
are more dominant than others. However, we suspect that this phenomenon can
occur even when modalities have comparable, or even equal, predictive
strengths. To demonstrate this idea, we look to ensembles. Specifically, we
train an ensemble of unimodal ReID models on a single modality. When training
ensembles, it is common practice to train each ensemble member individually
and fuse their predictions only at inference (i.e. bagging). We compare this
standard strategy of training each ensemble member independently (UniCat) with
training them jointly by having a global loss use their fused output embedding
(Fusion-avg/concat).

For this experiment, we investigate each modality within RGBNT100 as well as
the popular unimodal person ReID dataset, Market1501 [20]. We choose ViT-B as
our model backbone and use ImageNet pre-trained weights. The classifiers and
bottlenecks are randomly instantiated via [5], so that we may fully expect the
backbones to have unique final solutions.

As shown in Table 4, there is a boost in unimodal RGBNT100 ReID performance
for all ensemble models when compared to Table 2, which is expected as
ensembling helps to diminish the impacts of overfitting. However, what is
notable is that in all unimodal tasks, training the ensemble using a global
loss (Fusion-avg/concat) resulted in a lower performance than would otherwise
have been obtained if each member were trained independently (UniCat). This
underscores the fundamental nature by which modality laziness operates and how
the phenomenon should be considered even when training with balanced
modalities.

##  Appendix D RGBNT100 Training Performance

Figure 2: Comparison of train and test unimodal ReID performance for our late-
fusion mulitmodal baselines on RGBNT100.

To further distinguish whether modality laziness or general overfitting is at
play in the performance drop observed when training RGBNT100 with fusion, we
evaluate the unimodal ReID performance (given by mAP) of the train set for
RGBNT100 (see Figure 2). Mirroring the test behavior, we see that the unimodal
mAP for the train set was inhibited for Fusion-avg and Fusion-concat compared
to UniCat. Thus, contrary to the hypothesis of [14], the performance decline
that we observed when training with fusion (Table 1) can be primarily linked
to modality laziness, and it is actually UniCat that appears to be more at
risk for overfitting. This also helps to demonstrate how the impacts of
modality laziness may at times be beneficial for weaker, less-informative
modalities that are especially overfitting-prone, as we observed in RGBNT201
(Tables 1 and 3).