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.

A Fast and Fault-Tolerant Distributed Algorithm for Near-Optimal TDMA Scheduling in WSNs

The time division multiple access (TDMA) based channel access mechanisms perform better than the contention based channel access mechanisms, in terms of channel utilization, reliability and power consumption, specially for high data rate applications in wireless sensor networks (WSNs). Most of the existing distributed TDMA scheduling techniques can be classified as either static or dynamic. The primary purpose of static TDMA scheduling algorithms is to improve the channel utilization by generating a schedule of smaller length. But, they usually take longer time to schedule, and hence, are not suitable for WSNs, in which the network topology changes dynamically. On the other hand, dynamic TDMA scheduling algorithms generate a schedule quickly, but they are not efficient in terms of generated schedule length. In this paper, we propose a novel scheme for TDMA scheduling in WSNs, which can generate a compact schedule similar to static scheduling algorithms, while its runtime performance can be matched with those of dynamic scheduling algorithms. Furthermore, the proposed distributed TDMA scheduling algorithm has the capability to trade-off schedule length with the time required to generate the schedule. This would allow the developers of WSNs, to tune the performance, as per the requirement of prevalent WSN applications, and the requirement to perform re-scheduling. Finally, the proposed TDMA scheduling is fault-tolerant to packet loss due to erroneous wireless channel. The algorithm has been simulated using the Castalia simulator to compare its performance with those of others in terms of generated schedule length and the time required to generate the TDMA schedule. Simulation results show that the proposed algorithm generates a compact schedule in a very less time.

A Simple Label Switching Algorithm for Semisupervised Structural SVMs

In structured output learning, obtaining labeled data for real-world applications is usually costly, while unlabeled examples are available in abundance. Semisupervised structured classification deals with a small number of labeled examples and a large number of unlabeled structured data. In this work, we consider semisupervised structural support vector machines with domain constraints. The optimization problem, which in general is not convex, contains the loss terms associated with the labeled and unlabeled examples, along with the domain constraints. We propose a simple optimization approach that alternates between solving a supervised learning problem and a constraint matching problem. Solving the constraint matching problem is difficult for structured prediction, and we propose an efficient and effective label switching method to solve it. The alternating optimization is carried out within a deterministic annealing framework, which helps in effective constraint matching and avoiding poor local minima, which are not very useful. The algorithm is simple and easy to implement. Further, it is suitable for any structured output learning problem where exact inference is available. Experiments on benchmark sequence labeling data sets and a natural language parsing data set show that the proposed approach, though simple, achieves comparable generalization performance.

Evolutionary and structural analyses of heterodimeric proteins composed of subunits with same fold

Heterodimeric proteins with homologous subunits of same fold are involved in various biological processes. The objective of this study is to understand the evolution of structural and functional features of such heterodimers. Using a non-redundant dataset of 70 such heterodimers of known 3D structure and an independent dataset of 173 heterodimers from yeast, we note that the mean sequence identity between interacting homologous subunits is only 23-24% suggesting that, generally, highly diverged paralogues assemble to form such a heterodimer. We also note that the functional roles of interacting subunits/domains are generally quite different. This suggests that, though the interacting subunits/domains are homologous, the high evolutionary divergence characterize their high functional divergence which contributes to a gross function for the heterodimer considered as a whole. The inverse relationship between sequence identity and RMSD of interacting homologues in heterodimers is not followed. We also addressed the question of formation of homodimers of the subunits of heterodimers by generating models of fictitious homodimers on the basis of the 3D structures of the heterodimers. Interaction energies associated with these homodimers suggests that, in overwhelming majority of the cases, such homodimers are unlikely to be stable. Majority of the homologues of heterodimers of known structures form heterodimers (51.8%) and a small proportion (14.6%) form homodimers. Comparison of 3D structures of heterodimers with homologous homodimers suggests that interfacial nature of residues is not well conserved. In over 90% of the cases we note that the interacting subunits of heterodimers are co-localized in the cell. Proteins 2015; 83:1766-1786. (c) 2015 Wiley Periodicals, Inc.

An automatic algorithm for mixed mode crack growth rate based on drop potential method

A new automatic algorithm for the assessment of mixed mode crack growth rate characteristics is presented based on the concept of an equivalent crack. The residual ligament size approach is introduced to implementation this algorithm for identifying the crack tip position on a curved path with respect to the drop potential signal. The automatic algorithm accounting for the curvilinear crack trajectory and employing an electrical potential difference was calibrated with respect to the optical measurements for the growing crack under cyclic mixed mode loading conditions. The effectiveness of the proposed algorithm is confirmed by fatigue tests performed on ST3 steel compact tension-shear specimens in the full range of mode mixities from pure mode Ito pure mode II. (C) 2015 Elsevier Ltd. All rights reserved.

BT-benzo-29 inhibits bacterial cell proliferation by perturbing FtsZ assembly

We have identified a potent antibacterial agent N-(4-sec-butylphenyl)-2-(thiophen-2-yl)-1H-benzod]imidazole-4-carboxa mide (BT-benzo-29) from a library of benzimidazole derivatives that stalled bacterial division by inhibiting FtsZ assembly. A short (5 min) exposure of BT-benzo-29 disassembled the cytokinetic Z-ring in Bacillus subtilis cells without affecting the cell length and nucleoids. BT-benzo-29 also perturbed the localization of early and late division proteins such as FtsA, ZapA and SepF at the mid-cell. Further, BT-benzo-29 bound to FtsZ with a dissociation constant of 24 +/- 3 m and inhibited the assembly and GTPase activity of purified FtsZ. A docking analysis suggested that BT-benzo-29 may bind to FtsZ at the C-terminal domain near the T7 loop. BT-benzo-29 displayed significantly weaker inhibitory effects on the assembly and GTPase activity of two mutants (L272A and V275A) of FtsZ supporting the prediction of the docking analysis. Further, BT-benzo-29 did not appear to inhibit DNA duplication and nucleoid segregation and it did not perturb the membrane potential of B. subtilis cells. The results suggested that BT-benzo-29 exerts its potent antibacterial activity by inhibiting FtsZ assembly. Interestingly, BT-benzo-29 did not affect the membrane integrity of mammalian red blood cells. BT-benzo-29 bound to tubulin with a much weaker affinity than FtsZ and exerted significantly weaker effects on mammalian cells than on the bacterial cells indicating that the compound may have a strong antibacterial potential.

Systematic Analysis of Mycobacterial Acylation Reveals First Example of Acylation-mediated Regulation of Enzyme Activity of a Bacterial Phosphatase

Protein lysine acetylation is known to regulate multiple aspects of bacterial metabolism. However, its presence in mycobacterial signal transduction and virulence-associated proteins has not been studied. In this study, analysis of mycobacterial proteins from different cellular fractions indicated dynamic and widespread occurrence of lysine acetylation. Mycobacterium tuberculosis proteins regulating diverse physiological processes were then selected and expressed in the surrogate host Mycobacterium smegmatis. The purified proteins were analyzed for the presence of lysine acetylation, leading to the identification of 24 acetylated proteins. In addition, novel lysine succinylation and propionylation events were found to co-occur with acetylation on several proteins. Protein-tyrosine phosphatase B (PtpB), a secretory phosphatase that regulates phosphorylation of host proteins and plays a critical role in Mycobacterium infection, is modified by acetylation and succinylation at Lys-224. This residue is situated in a lid region that covers the enzyme's active site. Consequently, acetylation and succinylation negatively regulate the activity of PtpB.

Hybrid Working Set Algorithm for SVM Learning With a Kernel Coprocessor on FPGA

Support vector machines (SVM) are a popular class of supervised models in machine learning. The associated compute intensive learning algorithm limits their use in real-time applications. This paper presents a fully scalable architecture of a coprocessor, which can compute multiple rows of the kernel matrix in parallel. Further, we propose an extended variant of the popular decomposition technique, sequential minimal optimization, which we call hybrid working set (HWS) algorithm, to effectively utilize the benefits of cached kernel columns and the parallel computational power of the coprocessor. The coprocessor is implemented on Xilinx Virtex 7 field-programmable gate array-based VC707 board and achieves a speedup of upto 25x for kernel computation over single threaded computation on Intel Core i5. An application speedup of upto 15x over software implementation of LIBSVM and speedup of upto 23x over SVMLight is achieved using the HWS algorithm in unison with the coprocessor. The reduction in the number of iterations and sensitivity of the optimization time to variation in cache size using the HWS algorithm are also shown.

Recognizing drug targets using evolutionary information: implications for repurposing FDA-approved drugs against Mycobacterium tuberculosis H37Rv

Drug repurposing to explore target space has been gaining pace over the past decade with the upsurge in the use of systematic approaches for computational drug discovery. Such a cost and time-saving approach gains immense importance for pathogens of special interest, such as Mycobacterium tuberculosis H37Rv. We report a comprehensive approach to repurpose drugs, based on the exploration of evolutionary relationships inferred from the comparative sequence and structural analyses between targets of FDA-approved drugs and the proteins of M. tuberculosis. This approach has facilitated the identification of several polypharmacological drugs that could potentially target unexploited M. tuberculosis proteins. A total of 130 FDA-approved drugs, originally intended against other diseases, could be repurposed against 78 potential targets in M. tuberculosis. Additionally, we have also made an attempt to augment the chemical space by recognizing compounds structurally similar to FDA-approved drugs. For three of the attractive cases we have investigated the probable binding modes of the drugs in their corresponding M. tuberculosis targets by means of structural modelling. Such prospective targets and small molecules could be prioritized for experimental endeavours, and could significantly influence drug-discovery and drug-development programmes for tuberculosis.

A fast algorithm for speech polarity detection using long-term linear prediction

Speech polarity detection is a crucial first step in many speech processing techniques. In this paper, an algorithm is proposed that improvises the existing technique using the skewness of the voice source (VS) signal. Here, the integrated linear prediction residual (ILPR) is used as the VS estimate, which is obtained using linear prediction on long-term frames of the low-pass filtered speech signal. This excludes the unvoiced regions from analysis and also reduces the computation. Further, a modified skewness measure is proposed for decision, which also considers the magnitude of the skewness of the ILPR along with its sign. With the detection error rate (DER) as the performance metric, the algorithm is tested on 8 large databases and its performance (DER=0.20%) is found to be comparable to that of the best technique (DER=0.06%) on both clean and noisy speech. Further, the proposed method is found to be ten times faster than the best technique.

A Bacterial Foraging Optimization and Learning Automata Based Feature Selection for Motor Imagery EEG Classification

Selection of relevant features is an open problem in Brain-computer interfacing (BCI) research. Sometimes, features extracted from brain signals are high dimensional which in turn affects the accuracy of the classifier. Selection of the most relevant features improves the performance of the classifier and reduces the computational cost of the system. In this study, we have used a combination of Bacterial Foraging Optimization and Learning Automata to determine the best subset of features from a given motor imagery electroencephalography (EEG) based BCI dataset. Here, we have employed Discrete Wavelet Transform to obtain a high dimensional feature set and classified it by Distance Likelihood Ratio Test. Our proposed feature selector produced an accuracy of 80.291% in 216 seconds.

An evolutionary formalism for weak quantum measurements

Unitary evolution and projective measurement are fundamental axioms of quantum mechanics. Even though projective measurement yields one of the eigenstates of the measured operator as the outcome, there is no theory that predicts which eigenstate will be observed in which experimental run. There exists only an ensemble description, which predicts probabilities of various outcomes over many experimental runs. We propose a dynamical evolution equation for the projective collapse of the quantum state in individual experimental runs, which is consistent with the well-established framework of quantum mechanics. In case of gradual weak measurements, its predictions for ensemble evolution are different from those of the Born rule. It is an open question whether or not suitably designed experiments can observe this alternate evolution.

Prior image based temporally constrained reconstruction algorithm for magnetic resonance guided high intensity focused ultrasound

Purpose: A prior image based temporally constrained reconstruction ( PITCR) algorithm was developed for obtaining accurate temperature maps having better volume coverage, and spatial, and temporal resolution than other algorithms for highly undersampled data in magnetic resonance (MR) thermometry. Methods: The proposed PITCR approach is an algorithm that gives weight to the prior image and performs accurate reconstruction in a dynamic imaging environment. The PITCR method is compared with the temporally constrained reconstruction (TCR) algorithm using pork muscle data. Results: The PITCR method provides superior performance compared to the TCR approach with highly undersampled data. The proposed approach is computationally expensive compared to the TCR approach, but this could be overcome by the advantage of reconstructing with fewer measurements. In the case of reconstruction of temperature maps from 16% of fully sampled data, the PITCR approach was 1.57x slower compared to the TCR approach, while the root mean square error using PITCR is 0.784 compared to 2.815 with the TCR scheme. Conclusions: The PITCR approach is able to perform more accurate reconstructions of temperature maps compared to the TCR approach with highly undersampled data in MR guided high intensity focused ultrasound. (C) 2015 American Association of Physicists in Medicine.

Efficient density matrix renormalization group algorithm to study Y junctions with integer and half-integer spin

An efficient density matrix renormalization group (DMRG) algorithm is presented and applied to Y junctions, systems with three arms of n sites that meet at a central site. The accuracy is comparable to DMRG of chains. As in chains, new sites are always bonded to the most recently added sites and the superblock Hamiltonian contains only new or once renormalized operators. Junctions of up to N = 3n + 1 approximate to 500 sites are studied with antiferromagnetic (AF) Heisenberg exchange J between nearest-neighbor spins S or electron transfer t between nearest neighbors in half-filled Hubbard models. Exchange or electron transfer is exclusively between sites in two sublattices with N-A not equal N-B. The ground state (GS) and spin densities rho(r) = < S-r(z)> at site r are quite different for junctions with S = 1/2, 1, 3/2, and 2. The GS has finite total spin S-G = 2S(S) for even (odd) N and for M-G = S-G in the S-G spin manifold, rho(r) > 0(< 0) at sites of the larger (smaller) sublattice. S = 1/2 junctions have delocalized states and decreasing spin densities with increasing N. S = 1 junctions have four localized S-z = 1/2 states at the end of each arm and centered on the junction, consistent with localized states in S = 1 chains with finite Haldane gap. The GS of S = 3/2 or 2 junctions of up to 500 spins is a spin density wave with increased amplitude at the ends of arms or near the junction. Quantum fluctuations completely suppress AF order in S = 1/2 or 1 junctions, as well as in half-filled Hubbard junctions, but reduce rather than suppress AF order in S = 3/2 or 2 junctions.

l(1)-K-SVD: A robust dictionary learning algorithm with simultaneous update

We develop a new dictionary learning algorithm called the l(1)-K-svp, by minimizing the l(1) distortion on the data term. The proposed formulation corresponds to maximum a posteriori estimation assuming a Laplacian prior on the coefficient matrix and additive noise, and is, in general, robust to non-Gaussian noise. The l(1) distortion is minimized by employing the iteratively reweighted least-squares algorithm. The dictionary atoms and the corresponding sparse coefficients are simultaneously estimated in the dictionary update step. Experimental results show that l(1)-K-SVD results in noise-robustness, faster convergence, and higher atom recovery rate than the method of optimal directions, K-SVD, and the robust dictionary learning algorithm (RDL), in Gaussian as well as non-Gaussian noise. For a fixed value of sparsity, number of dictionary atoms, and data dimension, l(1)-K-SVD outperforms K-SVD and RDL on small training sets. We also consider the generalized l(p), 0 < p < 1, data metric to tackle heavy-tailed/impulsive noise. In an image denoising application, l(1)-K-SVD was found to result in higher peak signal-to-noise ratio (PSNR) over K-SVD for Laplacian noise. The structural similarity index increases by 0.1 for low input PSNR, which is significant and demonstrates the efficacy of the proposed method. (C) 2015 Elsevier B.V. All rights reserved.