match.bca {matchFeat}

Block Coordinate Ascent Method

Description

This function solves the multidimensional assignment problem with decomposable costs (MDADC) by block coordinate ascent. The dissimilarity function is the squared Euclidean distance.

Usage

match.bca(x, unit = NULL, w = NULL, 
	method = c("cyclical", "random"), control = list())

Arguments

x

data: matrix of dimensions (mn,p) or 3D array of dimensions (p,m,n) with m = number of labels/classes, n = number of sample units, and p = number of variables)

unit

integer (=number of units) or vector mapping rows of x to sample units (length mn). Must be specified only if x is a matrix.

w

weights for loss function: single positive number, p-vector of length, or (p,p) positive definite matrix

method

sweeping method for block coordinate ascent: cyclical or random (simple random sampling without replacement)

control

tuning parameters

Details

Given a set of n statistical units, each having m possibly mislabeled feature vectors, the one-to-one matching problem is to find a set of n label permutations that produce the best match of feature vectors across units. The objective function to minimize is the sum of (weighted) squared Euclidean distances between all pairs of feature vectors having the same (new) label. This amounts to minimizing the sum of the within-label variances. The sample means and sample covariances of the matched feature vectors are calculated as a post-processing step.

The block-coordinate ascent (BCA) algorithm successively sweeps through the statistical units (=blocks), each time relabeling the m feature vectors of a unit to best match those of the other n-1 units.

If x is a matrix, the rows should be sorted by increasing unit label and unit should be a nondecreasing sequence of integers, for example (1,...,1,2,...,2,...,n,...,n) with each integer 1,...,n replicated m times.

The argument w can be specified as a vector of positive numbers (will be recycled to length p if needed) or as a positive definite matrix of size (p,p).

The optional argument control is a list with three fields: sigma, starting point for the optimization ((m,n) matrix of permutations; maxit, maximum number of iterations; and equal.variance, logical value that specifies whether the returned sample covariance matrices V for matched features should be equal between labels/classes (TRUE) or label-specific (FALSE, default).

Value

A list of class matchFeat with components

sigma

best set of permutations for feature vectors ((m,n) matrix)

cluster

associated clusters (=inverse permutations)

objective

minimum objective value

mu

sample mean for each class/label ((p,m) matrix)

V

sample covariance for each class/label ((p,m) matrix

call

function call

References

Degras (2022) "Scalable feature matching across large data collections." doi:10.1080/10618600.2022.2074429
Wright (2015). Coordinate descent algorithms. https://arxiv.org/abs/1502.04759

See Also

match.2x, match.bca.gen, match.gaussmix, match.kmeans, match.rec, match.template

Examples

data(optdigits)
m <- length(unique(optdigits$label)) # number of classes
n <- nrow(optdigits$x) / m # number of units

## Use function with data in matrix form
fit1 <- match.bca(optdigits$x, unit=n)

## Use function with data in array form
p <- ncol(optdigits$x)
x <- t(optdigits$x)
dim(x) <- c(p,m,n)
fit2 <- match.bca(x)