Function eigenvalue_allocation

experiments/python/product_quantize.py:101–162

Compute a permutation of eigenvalues to balance variance accross buckets of dimensions. Described in section 3.2.4 in http://research.microsoft.com/pubs/187499/cvpr13opq.pdf Note, the following slides indicate this function will break when fed eigenvalues < 1 without the scaling

(num_buckets, eigenvalues, shuffle=False)

#
@_memory.cache
def eigenvalue_allocation(num_buckets, eigenvalues, shuffle=False):
    """
    Compute a permutation of eigenvalues to balance variance accross buckets
    of dimensions.
    Described in section 3.2.4 in http://research.microsoft.com/pubs/187499/cvpr13opq.pdf
    Note, the following slides indicate this function will break when fed eigenvalues < 1
    without the scaling trick implemented below:
        https://www.robots.ox.ac.uk/~vgg/rg/slides/ge__cvpr2013__optimizedpq.pdf
    :param int num_buckets:
        the number of dimension buckets over which to allocate eigenvalues
    :param ndarray eigenvalues:
        a vector of eigenvalues
    :param bool shuffle:
        whether to randomly shuffle the order of resulting buckets
    :returns ndarray:
        a vector of indices by which to permute the eigenvectors
    """
    D = len(eigenvalues)
    dims_per_bucket = D / num_buckets
    eigenvalue_product = np.zeros(num_buckets, dtype=float)
    bucket_size = np.zeros(num_buckets, dtype=int)
    permutation = np.zeros((num_buckets, dims_per_bucket), dtype=int)

    # We first must scale the eigenvalues by dividing by their
    # smallets non-zero value to avoid problems with the algorithm
    # when eigenvalues are less than 1.
    min_non_zero_eigenvalue = np.min(np.abs(eigenvalues[np.nonzero(eigenvalues)]))
    eigenvalues = eigenvalues / min_non_zero_eigenvalue

    # this is not actually a requirement, but I'm curious about whether this
    # condition is ever violated
    if not np.all(eigenvalues > 0):
        print "WARNING: some eigenvalues were nonpositive"

    # Iterate eigenvalues in descending order
    sorted_inds = np.argsort(eigenvalues)[::-1]
    log_eigs = np.log2(abs(eigenvalues))
    for ind in sorted_inds:

        # Find eligible (not full) buckets
        eligible = (bucket_size < dims_per_bucket).nonzero()

        # Find eligible bucket with least eigenvalue product
        i = eigenvalue_product[eligible].argmin(0)
        bucket = eligible[0][i]

        # Update eigenvalue product for this bucket
        eigenvalue_product[bucket] = eigenvalue_product[bucket] + log_eigs[ind]

        # Store bucket assignment and update size
        permutation[bucket, bucket_size[bucket]] = ind
        bucket_size[bucket] += 1

    if shuffle:
        shuffle_idxs = np.arange(num_buckets, dtype=np.int)
        np.random.shuffle(shuffle_idxs)
        permutation = permutation[shuffle_idxs]