A Split-and-Merge Dictionary Learning Algorithm for Sparse Representation: Application to Image Denoising

In big data image/video analytics, we encounter the problem of learning an over-complete dictionary for sparse representation from a large training dataset, which cannot be processed at once because of storage and computational constraints. To tackle the problem of dictionary learning in such scenarios, we propose an algorithm that exploits the inherent clustered structure of the training data and make use of a divide-and-conquer approach. The fundamental idea behind the algorithm is to partition the training dataset into smaller clusters, and learn local dictionaries for each cluster. Subsequently, the local dictionaries are merged to form a global dictionary. Merging is done by solving another dictionary learning problem on the atoms of the locally trained dictionaries. This algorithm is referred to as the split-and-merge algorithm. We show that the proposed algorithm is efficient in its usage of memory and computational complexity, and performs on par with the standard learning strategy, which operates on the entire data at a time. As an application, we consider the problem of image denoising. We present a comparative analysis of our algorithm with the standard learning techniques that use the entire database at a time, in terms of training and denoising performance. We observe that the split-and-merge algorithm results in a remarkable reduction of training time, without significantly affecting the denoising performance.

Region Segmentation via Deformable Model-Guided Split and Merge

An improved method for deformable shape-based image segmentation is described. Image regions are merged together and/or split apart, based on their agreement with an a priori distribution on the global deformation parameters for a shape template. The quality of a candidate region merging is evaluated by a cost measure that includes: homogeneity of image properties within the combined region, degree of overlap with a deformed shape model, and a deformation likelihood term. Perceptually-motivated criteria are used to determine where/how to split regions, based on the local shape properties of the region group's bounding contour. A globally consistent interpretation is determined in part by the minimum description length principle. Experiments show that the model-based splitting strategy yields a significant improvement in segmention over a method that uses merging alone.

Time Dependent Operator-split and Unsplit Schemes for One Dimensional Premixed Flames

This paper is concerned with a study of an operator split scheme and unsplit scheme for the computation of adiabatic freely propagating one-dimensional premixed flames. The study uses unsteady method for both split and unsplit schemes employing implicit chemistry and explicit diffusion, a combination which is stable and convergent. Solution scheme is not sensitive to the initial starting estimate and provides steady state even with straight line profiles (far from steady state) in small number of time steps. Two systems H2-Air and H2-NO (involving complex nitrogen chemistry) are considered in presentinvestigation. Careful comparison shows that the operator split approach is slightly superior than the unsplit when chemistry becomes complex. Comparison of computational times with those of existing steady and unsteady methods seems to suggest that the method employing implicit-explicit algorithm is very efficient and robust.

Rainbow colouring of split and threshold Graphs

A rainbow colouring of a connected graph is a colouring of the edges of the graph, such that every pair of vertices is connected by at least one path in which no two edges are coloured the same. Such a colouring using minimum possible number of colours is called an optimal rainbow colouring, and the minimum number of colours required is called the rainbow connection number of the graph. A Chordal Graph is a graph in which every cycle of length more than 3 has a chord. A Split Graph is a chordal graph whose vertices can be partitioned into a clique and an independent set. A threshold graph is a split graph in which the neighbourhoods of the independent set vertices form a linear order under set inclusion. In this article, we show the following: 1. The problem of deciding whether a graph can be rainbow coloured using 3 colours remains NP-complete even when restricted to the class of split graphs. However, any split graph can be rainbow coloured in linear time using at most one more colour than the optimum. 2. For every integer k ≥ 3, the problem of deciding whether a graph can be rainbow coloured using k colours remains NP-complete even when restricted to the class of chordal graphs. 3. For every positive integer k, threshold graphs with rainbow connection number k can be characterised based on their degree sequence alone. Further, we can optimally rainbow colour a threshold graph in linear time.

Learning from ordered sets and applications in collaborative ranking

Ranking over sets arise when users choose between groups of items. For example, a group may be of those movies deemed 5 stars to them, or a customized tour package. It turns out, to model this data type properly, we need to investigate the general combinatorics problem of partitioning a set and ordering the subsets. Here we construct a probabilistic log-linear model over a set of ordered subsets. Inference in this combinatorial space is highly challenging: The space size approaches (N!/2)6.93145N+1 as N approaches infinity. We propose a split-and-merge Metropolis-Hastings procedure that can explore the state-space efficiently. For discovering hidden aspects in the data, we enrich the model with latent binary variables so that the posteriors can be efficiently evaluated. Finally, we evaluate the proposed model on large-scale collaborative filtering tasks and demonstrate that it is competitive against state-of-the-art methods.

Habitat split and the global decline of amphibians

The worldwide decline in amphibians has been attributed to several causes, especially habitat loss and disease. We identified a further factor, namely habitat split- defined as human- induced disconnection between habitats used by different life history stages of a species- which forces forest- associated amphibians with aquatic larvae to make risky breeding migrations between suitable aquatic and terrestrial habitats. In the Brazilian Atlantic Forest, we found that habitat split negatively affects the richness of species with aquatic larvae but not the richness of species with terrestrial development ( the latter can complete their life cycle inside forest remnants). This mechanism helps to explain why species with aquatic larvae have the highest incidence of population decline. These findings reinforce the need for the conservation and restoration of riparian vegetation.

Functional split and crosslinking of the membrane domain of the β subunit of proton-translocating transhydrogenase from Escherichia coli

Proton pumping nicotinamide nucleotide transhydrogenase from Escherichia coli contains an α subunit with the NAD(H)-binding domain I and a β subunit with the NADP(H)-binding domain III. The membrane domain (domain II) harbors the proton channel and is made up of the hydrophobic parts of the α and β subunits. The interface in domain II between the α and the β subunits has previously been investigated by cross-linking loops connecting the four transmembrane helices in the α subunit and loops connecting the nine transmembrane helices in the β subunit. However, to investigate the organization of the nine transmembrane helices in the β subunit, a split was introduced by creating a stop codon in the loop connecting transmembrane helices 9 and 10 by a single mutagenesis step, utilizing an existing downstream start codon. The resulting enzyme was composed of the wild-type α subunit and the two new peptides β1 and β2. As compared to other split membrane proteins, the new transhydrogenase was remarkably active and catalyzed activities for the reduction of 3-acetylpyridine-NAD + by NADPH, the cyclic reduction of 3-acetylpyridine-NAD + by NADH (mediated by bound NADP(H)), and proton pumping, amounting to about 50-107% of the corresponding wild-type activities. These high activities suggest that the α subunit was normally folded, followed by a concerted folding of β1 + β2. Cross-linking of a βS105C-βS237C double cysteine mutant in the functional split cysteine-free background, followed by SDS-PAGE analysis, showed that helices 9, 13, and 14 were in close proximity. This is the first time that cross-linking between helices in the same β subunit has been demonstrated.