This study presents a technique for 2D tomography under unknown viewing angles when the distribution of the viewing angles is also unknown. Unknown view tomography (UVT) is a problem encountered in cryo-electron microscopy and in the geometric calibration of CT systems. There exists a moderate-sized literature on the 2D UVT problem, but most existing 2D UVT algorithms assume knowledge of the angle distribution which is not available usually. Our proposed methodology formulates the problem as an optimization task based on cross-validation error, to estimate the angle distribution jointly with the underlying 2D structure in an alternating fashion. We explore the algorithm’s capabilities for the case of two probability distribution models: a semi-parametric mixture of von Mises densities and a probability mass function model. We evaluate our algorithm’s performance under noisy projections using a PCAbased denoising technique and Graph Laplacian Tomography (GLT) driven by order statistics of the estimated distribution, to ensure near-perfect ordering, and compare our algorithm to intuitive baselines.

Unbalanced optimal transport (UOT) has recently gained much attention due to its flexible framework for handling un-normalized measures and its robustness properties. In this work, we explore learning (structured) sparse transport plans in the UOT setting, i.e., transport plans have an upper bound on the number of non-sparse entries in each column (structured sparse pattern) or in the whole plan (general sparse pattern). We propose novel sparsity-constrained UOT formulations building on the recently explored maximum mean discrepancy based UOT. We show that the proposed optimization problem is equivalent to the maximization of a weakly submodular function over a uniform matroid or a partition matroid. We develop efficient gradient-based discrete greedy algorithms and provide the corresponding theoretical guarantees. Empirically, we observe that our proposed greedy algorithms select a diverse support set and we illustrate the efficacy of the proposed approach in various applications.

Learning from positive ( P) and unlabeled ( U) data has a rich history as it finds use in multiple applications. In this paper, we provide a novel framework to tackle this problem in a model agnostic fashion. We say model agnostic since, our solution involves identifying and weighting positive as well as negative examples in an unsupervised manner which could then be passed as input to any standard classification algorithm. Moreover, based on our framework we provide approximation guarantees for our algorithm in terms of how well the identified positive examples from U along with their weights match the distribution of P. Such a principled approach has been missing for other methods that belong to the model agnostic category, not to mention that the current state-of-the-art are model dependent strategies that involve modifying the training algorithm. For Kernel Support Vector Machines, trained on a (non-negative) weighted dataset that as such is the output of our method, we derive generalization bounds. Given the advantages of having model agnostic methods (viz. use with (almost) any classifier, one time running cost), we show that our algorithm which possesses these benefits, is competitive with the best methods based on experiments on three real datasets. In fact, in a couple of cases we observe that our approach has better test performance than even standard supervised learning which has access to all positive as well as negative labels.

Prototypical examples that best summarize and compactly represent an underlying complex data distribution, communicate meaningful insights to humans in domains where simple explanations are hard to extract. In this paper, we present algorithms with strong theoretical guarantees to mine these data sets and select prototypes, a.k.a. representatives that optimally describes them. Our work notably generalizes the recent work by Kim et al. (2016) where in addition to selecting prototypes, we also associate non-negative weights which are indicative of their importance. This extension provides a single coherent framework under which both prototypes and criticisms (i.e. outliers) can be found. Furthermore, our framework works for any symmetric positive definite kernel thus addressing one of the key open questions laid out in Kim et al. (2016). By establishing that our objective function enjoys a key property of that of weak submodularity, we present a fast ProtoDash algorithm and also derive approximation guarantees for the same. We demonstrate the efficacy of our method on diverse domains such as retail, digit recognition (MNIST) and on publicly available 40 health questionnaires obtained from the Center for Disease Control (CDC) website maintained by the US Dept. of Health. We validate the results quantitatively as well as qualitatively based on expert feedback and recently published scientific studies on public health, thus showcasing the power of our technique in providing actionability (for retail), utility (for MNIST), and insight (on CDC datasets), which arguably are the hallmarks of an effective interpretable machine learning method.

This paper presents a method for improving the recovery guarantee for signals that are sparse or compressible in some general basis (dictionary) using a splitting and reordering approach. The splitting algorithm applies existing results for dictionaries that are naturally characterized as a concatenation of two sub-parts, to arbitrary dictionaries, by devising the optimal artificially induced split in the dictionary. A complete approach is presented for partitioning arbitrary dictionaries into two parts, so as to obtain the optimal coherence bounds on recovery, along with a proof of optimality. A heuristic is provided for recursive application of the splitting algorithm to further improve upon these bounds, using a multi-way dictionary split. We analyze cases where an appropriate split in the dictionary predicts less conservative signal sparsity bounds for successful recovery than those considering the dictionary as a monolithic block. Our present work does not provide a new algorithm for sparse signal recovery but rather mines for structures in the dictionary, towards strengthening the existing coherence-based recovery bounds.

Despite the ubiquitous use of distance transforms in the shape analysis literature and the popularity of fast marching and fast sweeping methods - essentially Hamilton-Jacobi solvers, there is very little recent work leveraging the Hamilton-Jacobi to Schrödinger connection for representational and computational purposes. In this work, we exploit the linearity of the Schrödinger equation to (i) design fast discrete convolution methods using the FFT to compute the distance transform, (ii) derive the histogram of oriented gradients (HOG) via the squared magnitude of the Fourier transform of the wave function, (iii) extend the Schrödinger formalism to cover the case of curves parametrized as line segments as opposed to point-sets, (iv) demonstrate that the Schrödinger formalism permits the addition of wave functions - an operation that is not allowed for distance transforms, and finally (v) construct a fundamentally new Schrödinger equation and show that it can represent both the distance transform and its gradient density - not possible in earlier efforts.

A compressive sensing framework is described for hyperspectral imaging. It is based on the widely used linear mixing model,LMM, which represents hyperspectral pixels as convex combinations of small numbers of endmember (material) spectra. The coefficients of the endmembers for each pixel are called proportions. The endmembers and proportions are often the sought-after quantities; the full image is an intermediate representation used to calculate them. Here, a method for estimating proportions and endmembers directly from compressively sensed hyperspectral data based onLMMis shown. Consequently, proportions and endmembers can be calculated directly from compressively sensed data with no need to reconstruct full hyperspectral images. If spectral information is required, endmembers can be reconstructed using compressive sensing reconstruction algorithms. Furthermore, given known endmembers, the proportions of the associated materials can be measured directly using a compressive sensing imaging device. This device would produce a multiband image; the bands would directly represent the material proportions.

Summary form only given. We present efficient machine learning methods for color image compression which simultaneously learn bases for compact image representation as well as the color space. We show the benefits of representing color image patches as 2D matrices of size n × 3n rather than as 3D patches of size n × n × 3. We also present a method to leverage greater representational power from a learned dictionary without increasing its size.

We present a new method for compact representation of large image datasets. Our method is based on treating small patches from a 2-D image as matrices as opposed to the conventional vectorial representation, and encoding these patches as sparse projections onto a set of exemplar orthonormal bases, which are learned a priori from a training set. The end result is a low-error, highly compact image/patch representation that has significant theoretical merits and compares favorably with existing techniques (including JPEG) on experiments involving the compression of ORL and Yale face databases, as well as a database of miscellaneous natural images. In the context of learning multiple orthonormal bases, we show the easy tunability of our method to efficiently represent patches of different complexities. Furthermore, we show that our method is extensible in a theoretically sound manner to higher-order matrices ("tensors"). We demonstrate applications of this theory to compression of well-known color image datasets such as the GaTech and CMU-PIE face databases and show performance competitive with JPEG. Lastly, we also analyze the effect of image noise on the performance of our compression schemes.

We present a new method for compact representation of large image datasets. Our method is based on treating small patches from an image as matrices as opposed to the conventional vectorial representation, and encoding those patches as sparse projections onto a set of exemplar orthonormal bases, which are learned a priori from a training set. The end result is a low-error, highly compact image/patch representation that has significant theoretical merits and compares favorably with existing techniques on experiments involving the compression of ORL and Yale face databases.