results for au:Cheng_L in:cs

- Selecting the right drugs for the right patients is a primary goal of precision medicine. In this manuscript, we consider the problem of cancer drug selection in a learning-to-rank framework. We have formulated the cancer drug selection problem as to accurately predicting 1). the ranking positions of sensitive drugs and 2). the ranking orders among sensitive drugs in cancer cell lines based on their responses to cancer drugs. We have developed a new learning-to-rank method, denoted as pLETORg , that predicts drug ranking structures in each cell line via using drug latent vectors and cell line latent vectors. The pLETORg method learns such latent vectors through explicitly enforcing that, in the drug ranking list of each cell line, the sensitive drugs are pushed above insensitive drugs, and meanwhile the ranking orders among sensitive drugs are correct. Genomics information on cell lines is leveraged in learning the latent vectors. Our experimental results on a benchmark cell line-drug response dataset demonstrate that the new pLETORg significantly outperforms the state-of-the-art method in prioritizing new sensitive drugs.
- In this paper, we consider solving a class of nonconvex and nonsmooth problems frequently appearing in signal processing and machine learning research. The traditional alternating direction method of multipliers encounter troubles in both mathematics and computations in solving the nonconvex and nonsmooth subproblem. In view of this, we propose a reweighted alternating direction method of multipliers. In this algorithm, all subproblems are convex and easy to calculate. We also provide several guarantees for the convergence and prove that the algorithm globally converges to a critical point of an auxiliary function with the help of the Kurdyka- Lojasiewicz property. Several numerical results are presented to demonstrate the efficiency of the proposed algorithm.
- Sep 04 2017 cs.CV arXiv:1709.00235v1A major bottleneck of pedestrian detection lies on the sharp performance deterioration in the presence of small-size pedestrians that are relatively far from the camera. Motivated by the observation that pedestrians of disparate spatial scales exhibit distinct visual appearances, we propose in this paper an active pedestrian detector that explicitly operates over multiple-layer neuronal representations of the input still image. More specifically, convolutional neural nets such as ResNet and faster R-CNNs are exploited to provide a rich and discriminative hierarchy of feature representations as well as initial pedestrian proposals. Here each pedestrian observation of distinct size could be best characterized in terms of the ResNet feature representation at a certain layer of the hierarchy; Meanwhile, initial pedestrian proposals are attained by faster R-CNNs techniques, i.e. region proposal network and follow-up region of interesting pooling layer employed right after the specific ResNet convolutional layer of interest, to produce joint predictions on the bounding-box proposals' locations and categories (i.e. pedestrian or not). This is engaged as input to our active detector where for each initial pedestrian proposal, a sequence of coordinate transformation actions is carried out to determine its proper x-y 2D location and layer of feature representation, or eventually terminated as being background. Empirically our approach is demonstrated to produce overall lower detection errors on widely-used benchmarks, and it works particularly well with far-scale pedestrians. For example, compared with 60.51% log-average miss rate of the state-of-the-art MS-CNN for far-scale pedestrians (those below 80 pixels in bounding-box height) of the Caltech benchmark, the miss rate of our approach is 41.85%, with a notable reduction of 18.68%.
- Jun 08 2017 cs.CV arXiv:1706.02185v1This paper aims at synthesizing filamentary structured images such as retinal fundus images and neuronal images, as follows: Given a ground-truth, to generate multiple realistic looking phantoms. A ground-truth could be a binary segmentation map containing the filamentary structured morphology, while the synthesized output image is of the same size as the ground-truth and has similar visual appearance to what have been presented in the training set. Our approach is inspired by the recent progresses in generative adversarial nets (GANs) as well as image style transfer. In particular, it is dedicated to our problem context with the following properties: Rather than large-scale dataset, it works well in the presence of as few as 10 training examples, which is common in medical image analysis; It is capable of synthesizing diverse images from the same ground-truth; Last and importantly, the synthetic images produced by our approach are demonstrated to be useful in boosting image analysis performance. Empirical examination over various benchmarks of fundus and neuronal images demonstrate the advantages of the proposed approach.
- Apr 24 2017 cs.AI arXiv:1704.06300v1The management of invasive mechanical ventilation, and the regulation of sedation and analgesia during ventilation, constitutes a major part of the care of patients admitted to intensive care units. Both prolonged dependence on mechanical ventilation and premature extubation are associated with increased risk of complications and higher hospital costs, but clinical opinion on the best protocol for weaning patients off of a ventilator varies. This work aims to develop a decision support tool that uses available patient information to predict time-to-extubation readiness and to recommend a personalized regime of sedation dosage and ventilator support. To this end, we use off-policy reinforcement learning algorithms to determine the best action at a given patient state from sub-optimal historical ICU data. We compare treatment policies from fitted Q-iteration with extremely randomized trees and with feedforward neural networks, and demonstrate that the policies learnt show promise in recommending weaning protocols with improved outcomes, in terms of minimizing rates of reintubation and regulating physiological stability.
- We consider the topic of multivariate regression on manifold-valued output, that is, for a multivariate observation, its output response lies on a manifold. Moreover, we propose a new regression model to deal with the presence of grossly corrupted manifold-valued responses, a bottleneck issue commonly encountered in practical scenarios. Our model first takes a correction step on the grossly corrupted responses via geodesic curves on the manifold, and then performs multivariate linear regression on the corrected data. This results in a nonconvex and nonsmooth optimization problem on manifolds. To this end, we propose a dedicated approach named PALMR, by utilizing and extending the proximal alternating linearized minimization techniques. Theoretically, we investigate its convergence property, where it is shown to converge to a critical point under mild conditions. Empirically, we test our model on both synthetic and real diffusion tensor imaging data, and show that our model outperforms other multivariate regression models when manifold-valued responses contain gross errors, and is effective in identifying gross errors.
- This paper studies the problem of multivariate linear regression where a portion of the observations is grossly corrupted or is missing, and the magnitudes and locations of such occurrences are unknown in priori. To deal with this problem, we propose a new approach by explicitly consider the error source as well as its sparseness nature. An interesting property of our approach lies in its ability of allowing individual regression output elements or tasks to possess their unique noise levels. Moreover, despite working with a non-smooth optimization problem, our approach still guarantees to converge to its optimal solution. Experiments on synthetic data demonstrate the competitiveness of our approach compared with existing multivariate regression models. In addition, empirically our approach has been validated with very promising results on two exemplar real-world applications: The first concerns the prediction of \textitBig-Five personality based on user behaviors at social network sites (SNSs), while the second is 3D human hand pose estimation from depth images. The implementation of our approach and comparison methods as well as the involved datasets are made publicly available in support of the open-source and reproducible research initiatives.
- Complex activity recognition is challenging due to the inherent uncertainty and diversity of performing a complex activity. Normally, each instance of a complex activity has its own configuration of atomic actions and their temporal dependencies. We propose in this paper an atomic action-based Bayesian model that constructs Allen's interval relation networks to characterize complex activities with structural varieties in a probabilistic generative way: By introducing latent variables from the Chinese restaurant process, our approach is able to capture all possible styles of a particular complex activity as a unique set of distributions over atomic actions and relations. We also show that local temporal dependencies can be retained and are globally consistent in the resulting interval network. Moreover, network structure can be learned from empirical data. A new dataset of complex hand activities has been constructed and made publicly available, which is much larger in size than any existing datasets. Empirical evaluations on benchmark datasets as well as our in-house dataset demonstrate the competitiveness of our approach.
- Dec 05 2016 cs.CV arXiv:1612.00596v1This paper focuses on the challenging problem of 3D pose estimation of a diverse spectrum of articulated objects from single depth images. A novel structured prediction approach is considered, where 3D poses are represented as skeletal models that naturally operate on manifolds. Given an input depth image, the problem of predicting the most proper articulation of underlying skeletal model is thus formulated as sequentially searching for the optimal skeletal configuration. This is subsequently addressed by convolutional neural nets trained end-to-end to render sequential prediction of the joint locations as regressing a set of tangent vectors of the underlying manifolds. Our approach is examined on various articulated objects including human hand, mouse, and fish benchmark datasets. Empirically it is shown to deliver highly competitive performance with respect to the state-of-the-arts, while operating in real-time (over 30 FPS).
- Oct 12 2016 cs.NI arXiv:1610.03348v1We consider the shortest path routing (SPR) of a network with stochastically time varying link metrics under potential adversarial attacks. Due to potential denial of service attacks, the distributions of link states could be stochastic (benign) or adversarial at different temporal and spatial locations. Without any \empha priori, designing an adaptive SPR protocol to cope with all possible situations in practice optimally is a very challenging issue. In this paper, we present the first solution by formulating it as a multi-armed bandit (MAB) problem. By introducing a novel control parameter into the exploration phase for each link, a martingale inequality is applied in the our combinatorial adversarial MAB framework. As such, our proposed algorithms could automatically detect features of the environment within a unified framework and find the optimal SPR strategies with almost optimal learning performance in all possible cases over time. Moreover, we study important issues related to the practical implementation, such as decoupling route selection with multi-path route probing, cooperative learning among multiple sources, the "cold-start" issue and delayed feedback of our algorithm. Nonetheless, the proposed SPR algorithms can be implemented with low complexity and they are proved to scale very well with the network size. Comparing to existing approaches in a typical network scenario under jamming attacks, our algorithm has a 65.3\% improvement of network delay given a learning period and a 81.5\% improvement of learning duration under a specified network delay.
- Sep 14 2016 cs.CV arXiv:1609.03773v1Pose estimation, tracking, and action recognition of articulated objects from depth images are important and challenging problems, which are normally considered separately. In this paper, a unified paradigm based on Lie group theory is proposed, which enables us to collectively address these related problems. Our approach is also applicable to a wide range of articulated objects. Empirically it is evaluated on lab animals including mouse and fish, as well as on human hand. On these applications, it is shown to deliver competitive results compared to the state-of-the-arts, and non-trivial baselines including convolutional neural networks and regression forest methods.
- Jun 08 2016 cs.CV arXiv:1606.02031v1Detecting hand actions from ego-centric depth sequences is a practically challenging problem, owing mostly to the complex and dexterous nature of hand articulations as well as non-stationary camera motion. We address this problem via a Hough transform based approach coupled with a discriminatively learned error-correcting component to tackle the well known issue of incorrect votes from the Hough transform. In this framework, local parts vote collectively for the start $\&$ end positions of each action over time. We also construct an in-house annotated dataset of 300 long videos, containing 3,177 single-action subsequences over 16 action classes collected from 26 individuals. Our system is empirically evaluated on this real-life dataset for both the action recognition and detection tasks, and is shown to produce satisfactory results. To facilitate reproduction, the new dataset and our implementation are also provided online.
- Nov 25 2015 cs.CV arXiv:1511.07611v1We focus on the challenging problem of efficient mouse 3D pose estimation based on static images, and especially single depth images. We introduce an approach to discriminatively train the split nodes of trees in random forest to improve their performance on estimation of 3D joint positions of mouse. Our algorithm is capable of working with different types of rodents and with different types of depth cameras and imaging setups. In particular, it is demonstrated in this paper that when a top-mounted depth camera is combined with a bottom-mounted color camera, the final system is capable of delivering full-body pose estimation including four limbs and the paws. Empirical examinations on synthesized and real-world depth images confirm the applicability of our approach on mouse pose estimation, as well as the closely related task of part-based labeling of mouse.
- Aug 28 2015 cs.SY arXiv:1508.06927v1This note further studies the previously proposed consensus protocol for linear multi-agent systems with communication noises in [15], [16]. Each agent is allowed to have its own time-varying gain to attenuate the effect of communication noises. Therefore, the common assumption in most references that all agents have the same noise-attenuation gain is not necessary. It has been proved that if all noise-attenuation gains are infinitesimal of the same order, then the mean square leader-following consensus can be reached. Furthermore, the convergence rate of the multi-agent system has been investigated. If the noise-attenuation gains belong to a class of functions which are bounded above and below by $t^{-\beta}$ $(\beta\in(0,1))$ asymptotically, then the states of all follower agents are convergent in mean square to the leader's state with the rate characterized by a function bounded above by $t^{-\beta}$ asymptotically.
- Correlated sources are present in communication systems where protocols ensure that there is some predetermined information for sources. Here correlated sources across an eavesdropped channel that incorporate a heterogeneous encoding scheme and their effect on the information leakage when some channel information and a source have been wiretapped is investigated. The information leakage bounds for the Slepian-Wolf scenario are provided. Thereafter, the Shannon cipher system approach is presented. Further, an implementation method using a matrix partition approach is described.
- Nov 18 2014 cs.SY arXiv:1411.4346v3This paper studies the containment control problem of multi-agent systems with multiple dynamic leaders in both the discrete-time domain and the continuous-time domain. The leaders' motions are described by $(n-1)$-order polynomial trajectories. This setting makes practical sense because given some critical points, the leaders' trajectories are usually planned by the polynomial interpolations. In order to drive all followers into the convex hull spanned by the leaders, a $PI^n$-type ($P$ and $I$ are short for \it Proportion and \it Integration, respectively; $I^n$ implies that the algorithm includes high-order integral terms) containment algorithm is proposed. It is theoretically proved that the $PI^n$-type containment algorithm is able to solve the containment problem of multi-agent systems where the followers are described by any order integral dynamics. Compared with the previous results on the multi-agent systems with dynamic leaders, the distinguished features of this paper are that: (1) the containment problem is studied not only in the continuous-time domain but also in the discrete-time domain while most existing results only work in the continuous-time domain; (2) to deal with the leaders with the $(n-1)$-order polynomial trajectories, existing results require the follower's dynamics to be $n$-order integral while the followers considered in this paper can be described by any-order integral; and (3) the "sign" function is not employed in the proposed algorithm, which avoids the chattering phenomenon. Furthermore, in order to illustrate the practical value of the proposed approach, an application, the containment control of multiple mobile robots is studied. Finally, two simulation examples are given to demonstrate the effectiveness of the proposed algorithm.
- Correlated sources are present in communication systems where protocols ensure that there is some predetermined information for sources to transmit. Here, two correlated sources across a channel with eavesdroppers are investigated, and conditions for perfect secrecy when some channel information and some source data symbols (the predetermined information) have been wiretapped are determined. The adversary in this situation has access to more information than if a link is wiretapped only and can thus determine more about a particular source. This scenario caters for an application where the eavesdropper has access to some preexisting information. We provide bounds for the channel and key rates for this scenario. Further, we provide a method to reduce the key lengths required for perfect secrecy.
- May 06 2014 cs.DS arXiv:1405.0712v1In this paper, we consider the slack due-window assignment model and study a single machine scheduling problem of linear time-dependent deteriorating jobs and a deteriorating maintenance activity. The cost for each job consists of four components: earliness, tardiness, window location and window size. The objective is to schedule the jobs and to assign the maintenance activity and due-windows such that the total cost among all the jobs is minimized. A polynomial-time algorithm with the running time not exceeding $O(n^2logn)$ to give a solution to this problem is introduced, where $n$ is the number of jobs.
- For solving a wide class of nonconvex and nonsmooth problems, we propose a proximal linearized iteratively reweighted least squares (PL-IRLS) algorithm. We ?rst approximate the original problem by smoothing methods, and second write the approximated problem into an auxiliary problem by introducing new variables. PL-IRLS is then built on solving the auxiliary problem by utilizing the proximal linearization technique and the iteratively reweighted least squares (IRLS) method, and has remarkable computation advantages. We show that PL-IRLS can be extended to solve more general nonconvex and nonsmooth problems via adjusting generalized parameters, and also to solve nonconvex and nonsmooth problems with two or more blocks of variables. Theoretically, with the help of the Kurdyka- Lojasiewicz property, we prove that each bounded sequence generated by PL-IRLS globally converges to a critical point of the approximated problem. To the best of our knowledge, this is the ?rst global convergence result of applying IRLS idea to solve nonconvex and nonsmooth problems. At last, we apply PL-IRLS to solve three representative nonconvex and nonsmooth problems in sparse signal recovery and low-rank matrix recovery and obtain new globally convergent algorithms.
- Mar 12 2014 cs.DC arXiv:1403.2404v1The Semantic Web comprises enormous volumes of semi-structured data elements. For interoperability, these elements are represented by long strings. Such representations are not efficient for the purposes of Semantic Web applications that perform computations over large volumes of information. A typical method for alleviating the impact of this problem is through the use of compression methods that produce more compact representations of the data. The use of dictionary encoding for this purpose is particularly prevalent in Semantic Web database systems. However, centralized implementations present performance bottlenecks, giving rise to the need for scalable, efficient distributed encoding schemes. In this paper, we describe an encoding implementation based on the asynchronous partitioned global address space (APGAS) parallel programming model. We evaluate performance on a cluster of up to 384 cores and datasets of up to 11 billion triples (1.9 TB). Compared to the state-of-art MapReduce algorithm, we demonstrate a speedup of 2.6-7.4x and excellent scalability. These results illustrate the strong potential of the APGAS model for efficient implementation of dictionary encoding and contributes to the engineering of larger scale Semantic Web applications.
- In this paper, we consider the second-order consensus problem for networked mechanical systems subjected to nonuniform communication delays, and the mechanical systems are assumed to interact on a general directed topology. We propose an adaptive controller plus a distributed velocity observer to realize the objective of second-order consensus. It is shown that both the positions and velocities of the mechanical agents synchronize, and furthermore, the velocities of the mechanical agents converge to the scaled weighted average value of their initial ones. We further demonstrate that the proposed second-order consensus scheme can be used to solve the leader-follower synchronization problem with a constant-velocity leader and under constant communication delays. Simulation results are provided to illustrate the performance of the proposed adaptive controllers.
- In this paper we consider the problem of graph-based transductive classification, and we are particularly interested in the directed graph scenario which is a natural form for many real world applications. Different from existing research efforts that either only deal with undirected graphs or circumvent directionality by means of symmetrization, we propose a novel random walk approach on directed graphs using absorbing Markov chains, which can be regarded as maximizing the accumulated expected number of visits from the unlabeled transient states. Our algorithm is simple, easy to implement, and works with large-scale graphs. In particular, it is capable of preserving the graph structure even when the input graph is sparse and changes over time, as well as retaining weak signals presented in the directed edges. We present its intimate connections to a number of existing methods, including graph kernels, graph Laplacian based methods, and interestingly, spanning forest of graphs. Its computational complexity and the generalization error are also studied. Empirically our algorithm is systematically evaluated on a wide range of applications, where it has shown to perform competitively comparing to a suite of state-of-the-art methods.
- A new generalised approach for multiple correlated sources over a wiretap network is investigated. Shannon's cipher system with eavesdroppers is incorporated into the model. The model is detailed using two sources, $X$ and $Y$ where each produce a component of the common information between them, before being extended for multiple correlated sources. There are several cases considered on whether syndromes on the channels are wiretapped, and based on this a new quantity, the information leakage at the source/s are determined. An interesting feature of the novel, generalised model is the quantification of the information leakage. It is of benefit to know which terms contribute the most to the information leakage so they can be secured even further. Here, we find that the common informations contribute the most to information leakage. A new scheme that incorporates masking using common informations to reduce the information leakage is presented and applied to the generalised model.
- This paper analyzes circulant Johnson-Lindenstrauss (JL) embeddings which, as an important class of structured random JL embeddings, are formed by randomizing the column signs of a circulant matrix generated by a random vector. With the help of recent decoupling techniques and matrix-valued Bernstein inequalities, we obtain a new bound $k=O(\epsilon^{-2}\log^{(1+\delta)} (n))$ for Gaussian circulant JL embeddings. Moreover, by using the Laplace transform technique (also called Bernstein's trick), we extend the result to subgaussian case. The bounds in this paper offer a small improvement over the current best bounds for Gaussian circulant JL embeddings for certain parameter regimes and are derived using more direct methods.
- Convex optimization models find interesting applications, especially in signal/image processing and compressive sensing. We study some augmented convex models, which are perturbed by strongly convex functions, and propose a dual gradient algorithm. The proposed algorithm includes the linearized Bregman algorithm and the singular value thresholding algorithm as special cases. Based on fundamental properties of proximal operators, we present a concise approach to establish the convergence of both primal and dual sequences, improving the results in the existing literature.
- Owing to the edge preserving ability and low computational cost of the total variation (TV), variational models with the TV regularization have been widely investigated in the field of multiplicative noise removal. The key points of the successful application of these models lie in: the optimal selection of the regularization parameter which balances the data-fidelity term with the TV regularizer; the efficient algorithm to compute the solution. In this paper, we propose two fast algorithms based on the linearized technique, which are able to estimate the regularization parameter and recover the image simultaneously. In the iteration step of the proposed algorithms, the regularization parameter is adjusted by a special discrepancy function defined for multiplicative noise. The convergence properties of the proposed algorithms are proved under certain conditions, and numerical experiments demonstrate that the proposed algorithms overall outperform some state-of-the-art methods in the PSNR values and computational time.
- May 15 2013 cs.CV arXiv:1305.3013v1Wavelet domain inpainting refers to the process of recovering the missing coefficients during the image compression or transmission stage. Recently, an efficient algorithm framework which is called Bregmanized operator splitting (BOS) was proposed for solving the classical variational model of wavelet inpainting. However, it is still time-consuming to some extent due to the inner iteration. In this paper, a novel variational model is established to formulate this reconstruction problem from the view of image decomposition. Then an efficient iterative algorithm based on the split-Bregman method is adopted to calculate an optimal solution, and it is also proved to be convergent. Compared with the BOS algorithm the proposed algorithm avoids the inner iteration and hence is more simple. Numerical experiments demonstrate that the proposed method is very efficient and outperforms the current state-of-the-art methods, especially in the computational time.
- Apr 16 2013 cs.SY arXiv:1304.3972v1Consensus problem of high-order integral multi-agent systems under switching directed topology is considered in this study. Depending on whether the agent's full state is available or not, two distributed protocols are proposed to ensure that states of all agents can be convergent to a same stationary value. In the proposed protocols, the gain vector associated with the agent's (estimated) state and the gain vector associated with the relative (estimated) states between agents are designed in a sophisticated way. By this particular design, the high-order integral multi-agent system can be transformed into a first-order integral multi-agent system. And the convergence of the transformed first-order integral agent's state indicates the convergence of the original high-order integral agent's state if and only if all roots of the polynomial, whose coefficients are the entries of the gain vector associated with the relative (estimated) states between agents, are in the open left-half complex plane. Therefore, many analysis techniques in the first-order integral multi-agent system can be directly borrowed to solve the problems in the high-order integral multi-agent system. Due to this property, it is proved that to reach a consensus, the switching directed topology of multi-agent system is only required to be "uniformly jointly quasi-strongly connected", which seems the mildest connectivity condition in the literature. In addition, the consensus problem of discrete-time high-order integral multi-agent systems is studied. The corresponding consensus protocol and performance analysis are presented. Finally, three simulation examples are provided to show the effectiveness of the proposed approach.
- This paper shows that the solutions to various convex $\ell_1$ minimization problems are \emphunique if and only if a common set of conditions are satisfied. This result applies broadly to the basis pursuit model, basis pursuit denoising model, Lasso model, as well as other $\ell_1$ models that either minimize $f(Ax-b)$ or impose the constraint $f(Ax-b)\leq\sigma$, where $f$ is a strictly convex function. For these models, this paper proves that, given a solution $x^*$ and defining $I=\supp(x^*)$ and $s=\sign(x^*_I)$, $x^*$ is the unique solution if and only if $A_I$ has full column rank and there exists $y$ such that $A_I^Ty=s$ and $|a_i^Ty|_\infty<1$ for $i\not\in I$. This condition is previously known to be sufficient for the basis pursuit model to have a unique solution supported on $I$. Indeed, it is also necessary, and applies to a variety of other $\ell_1$ models. The paper also discusses ways to recognize unique solutions and verify the uniqueness conditions numerically.
- Apr 24 2012 cs.CY arXiv:1204.4809v1Many customer services are already available at Social Network Sites (SNSs), including user recommendation and media interaction, to name a few. There are strong desires to provide online users more dedicated and personalized services that fit into individual's need, usually strongly depending on the inner personalities of the user. However, little has been done to conduct proper psychological analysis, crucial for explaining the user's outer behaviors from their inner personality. In this paper, we propose an approach that intends to facilitate this line of research by directly predicting the so called Big-Five Personality from user's SNS behaviors. Comparing to the conventional inventory-based psychological analysis, we demonstrate via experimental studies that users' personalities can be predicted with reasonable precision based on their online behaviors. Except for proving some former behavior-personality correlation results, our experiments show that extraversion is positively related to one's status republishing proportion and neuroticism is positively related to the proportion of one's angry blogs (blogs making people angry).
- The common task in matrix completion (MC) and robust principle component analysis (RPCA) is to recover a low-rank matrix from a given data matrix. These problems gained great attention from various areas in applied sciences recently, especially after the publication of the pioneering works of Cand`es et al.. One fundamental result in MC and RPCA is that nuclear norm based convex optimizations lead to the exact low-rank matrix recovery under suitable conditions. In this paper, we extend this result by showing that strongly convex optimizations can guarantee the exact low-rank matrix recovery as well. The result in this paper not only provides sufficient conditions under which the strongly convex models lead to the exact low-rank matrix recovery, but also guides us on how to choose suitable parameters in practical algorithms.
- As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the `labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.