TASK DEFINITION: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
PROBLEM: Joint matching over a collection of objects aims at aggregating information from a large collection of similar instances (e.g. images, graphs, shapes) to improve maps between pairs of them. Given multiple objects and matches computed between a few object pairs in isolation, the goal is to recover an entire collection of maps that are (1) globally consistent, and (2) close to the provided maps — and under certain conditions provably the ground-truth maps. Despite recent advances on this problem, the best-known recovery guarantees are limited to a small constant barrier — none of the existing methods find theoretical support when more than 50% of input correspondences are corrupted. Moreover, prior approaches focus mostly on fully similar objects, while it is practically more demanding to match instances that are only partially similar to each other (e.g., different views of a single physical object). In this paper, we propose an algorithm to jointly match multiple objects that exhibit only partial similarities, given a few (possibly highly incomplete) pairwise matches that are densely corrupted. By encoding a consistent partial map collection into a 0-1 semidefinite matrix, we propose to recover the ground-truth maps via a parameter-free convex program called MatchLift, following a spectral method that pre-estimates the total number of distinct elements to be matched. Numerically, this program can be efficiently solved via alternating direction methods of multipliers (ADMM) along with a greedy rounding strategy. Theoretically, MatchLift exhibits near-optimal error-correction ability, i.e. in the asymptotic regime it is guaranteed to work even when a dominant fraction 1 − Θ ( log n √ n ) of the input maps behave like random outliers. Furthermore, MatchLift succeeds with minimal input complexity, namely, perfect matching can be achieved as soon as the provided maps form a connected map graph. We evaluate the proposed algorithm on various benchmark data sets including synthetic examples and real-world examples, all of which confirm the practical applicability and usefulness of MatchLift.

SOLUTION: Near-Optimal Joint Object Matching via Convex Relaxation

PROBLEM: In this paper we formulate the framework of recovering a hidden orthonormal basis given access to a<lb>certain “Basis Encoding Function”. We describe the class of Basis Encoding Functions (BEF), such that<lb>their local maxima on the unit sphere are in one-to-one correspondence with the basis elements. This<lb>description relies on a certain “hidden convexity” property of these functions. A number of theoretical<lb>and practical problems of recent interest can be interpreted as recovering a hidden basis from potentially<lb>noisy observations. Specifically, we show how our simple and general framework applies to Independent<lb>Component Analysis (ICA), tensor decompositions, spectral clustering and Gaussian mixture learning.<lb>We describe a new algorithm, “gradient iteration”, for provable recovery of the hidden basis. We<lb>provide a complete theoretical analysis of Gradient Iteration both for the exact case as well as for the<lb>case when the observed function is a perturbation of the “true” underlying BEF. In both cases we show<lb>convergence and complexity bounds polynomial in dimension and other relevant parameters, such as<lb>perturbation size. Our perturbation results can be considered as a very general non-linear version of<lb>the classical Davis-Kahan theorem for eigenvectors of perturbations of symmetric matrices. In addition<lb>we show that in the exact case the algorithm converges superlinearly and give conditions relating the<lb>degree of convergence to properties of the Basis Encoding Function. Our algorithm can be viewed as a<lb>generalization of the classical power iteration method for eigenanalysis of symmetric matrices as well as<lb>a generalization of power iterations for tensors. Moreover, the Gradient Iteration algorithm can be easily<lb>and efficiently implemented in practice.

SOLUTION: Learning a Hidden Basis Through Imperfect Measurements: An Algorithmic Primitive

PROBLEM: People exhibit a tendency to generalize a novel noun to the basic-level in a hierarchical taxonomy – a cognitively salient category such as “dog” – with the degree of generalization depending on the number and type of exemplars. Recently, a change in the presentation timing of exemplars has also been shown to have an effect, surprisingly reversing the prior observed pattern of basic-level generalization. We explore the precise mechanisms that could lead to such behavior by extending a computational model of word learning and word generalization to integrate cognitive processes of memory and attention. Our results show that the interaction of forgetting and attention to novelty, as well as sensitivity to both type and token frequencies of exemplars, enables the model to replicate the empirical results from different presentation timings. Our results reinforce the need to incorporate general cognitive processes within word learning models to better understand the range of observed behaviors in vocabulary acquisition.

SOLUTION:
The Interaction of Memory and Attention in Novel Word Generalization: A Computational Investigation