The paper presents the Kuhn-Tucker conditions and duality theory for the lexicographic minimization problem: iex m in{F (x)|x e R n,G (x )Rm , respectively. The lexicographic duality is then applied ...for problems with polynomials in the objectives and in the constraints.
This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix ...recovery. The analysis relies on a key technical tool, which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while yielding sharp results. It is shown that for any given constant t ≥ 4/3, in compressed sensing, δ tk A <; √((t-1)/t) guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l 1 minimization, and similarly, in affine rank minimization, δ tr M <; √((t-1)/t) ensures the exact reconstruction of all matrices with rank at most r in the noiseless case via the constrained nuclear norm minimization. In addition, for any ε > 0, δ tk A <; √( t-1 / t ) + ε is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar results also hold for matrix recovery. In addition, the conditions δ tk A <; √((t-)1/t) and δ tr M <; √((t-1)/t) are also shown to be sufficient, respectively, for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.
In this paper we present a basis selection method that can be used with ℓ1-minimization to adaptively determine the large coefficients of polynomial chaos expansions (PCE). The adaptive construction ...produces anisotropic basis sets that have more terms in important dimensions and limits the number of unimportant terms that increase mutual coherence and thus degrade the performance of ℓ1-minimization. The important features and the accuracy of basis selection are demonstrated with a number of numerical examples. Specifically, we show that for a given computational budget, basis selection produces a more accurate PCE than would be obtained if the basis were fixed a priori. We also demonstrate that basis selection can be applied with non-uniform random variables and can leverage gradient information.
A lot of works have shown that frobenius-norm-based representation (FNR) is competitive to sparse representation and nuclear-norm-based representation (NNR) in numerous tasks such as subspace ...clustering. Despite the success of FNR in experimental studies, less theoretical analysis is provided to understand its working mechanism. In this brief, we fill this gap by building the theoretical connections between FNR and NNR. More specially, we prove that: 1) when the dictionary can provide enough representative capacity, FNR is exactly NNR even though the data set contains the Gaussian noise, Laplacian noise, or sample-specified corruption and 2) otherwise, FNR and NNR are two solutions on the column space of the dictionary.
In this paper, in order to improve the Student's t-matching accuracy, a novel Kullback-Leibler divergence (KLD) minimization-based matching method is firstly proposed by minimizing the upper bound of ...the KLD between the true Student's t-density and the approximate Student's t-density. To improve the Student's t-modelling accuracy, a novel KLD minimization-based adaptive method is then proposed to estimate the scale matrices of Student's t-distributions, in which the modified evidence lower bound is maximized. A novel KLD minimization-based adaptive Student's t-filter is derived via combining the proposed Student's t-matching technique and the adaptive method. A manoeuvring target tracking example is provided to demonstrate the effectiveness and potential of the proposed filter.
We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems. Building on the powerful Kurdyka–Łojasiewicz ...property, we derive a self-contained convergence analysis framework and establish that each bounded sequence generated by PALM globally converges to a critical point. Our approach allows to analyze various classes of nonconvex-nonsmooth problems and related nonconvex proximal forward–backward algorithms with semi-algebraic problem’s data, the later property being shared by many functions arising in a wide variety of fundamental applications. A by-product of our framework also shows that our results are new even in the convex setting. As an illustration of the results, we derive a new and simple globally convergent algorithm for solving the sparse nonnegative matrix factorization problem.
This paper gives an overview of the majorization-minimization (MM) algorithmic framework, which can provide guidance in deriving problem-driven algorithms with low computational cost. A general ...introduction of MM is presented, including a description of the basic principle and its convergence results. The extensions, acceleration schemes, and connection to other algorithmic frameworks are also covered. To bridge the gap between theory and practice, upperbounds for a large number of basic functions, derived based on the Taylor expansion, convexity, and special inequalities, are provided as ingredients for constructing surrogate functions. With the pre-requisites established, the way of applying MM to solving specific problems is elaborated by a wide range of applications in signal processing, communications, and machine learning.
Sparse coding has achieved a great success in various image processing tasks. However, a benchmark to measure the sparsity of image patch/group is missing since sparse coding is essentially an ...NP-hard problem. This work attempts to fill the gap from the perspective of rank minimization. We firstly design an adaptive dictionary to bridge the gap between group-based sparse coding (GSC) and rank minimization. Then, we show that under the designed dictionary, GSC and the rank minimization problems are equivalent, and therefore the sparse coefficients of each patch group can be measured by estimating the singular values of each patch group. We thus earn a benchmark to measure the sparsity of each patch group because the singular values of the original image patch groups can be easily computed by the singular value decomposition (SVD). This benchmark can be used to evaluate performance of any kind of norm minimization methods in sparse coding through analyzing their corresponding rank minimization counterparts. Towards this end, we exploit four well-known rank minimization methods to study the sparsity of each patch group and the weighted Schatten p-norm minimization (WSNM) is found to be the closest one to the real singular values of each patch group. Inspired by the aforementioned equivalence regime of rank minimization and GSC, WSNM can be translated into a non-convex weighted ℓp-norm minimization problem in GSC. By using the earned benchmark in sparse coding, the weighted ℓp-norm minimization is expected to obtain better performance than the three other norm minimization methods, i.e., ℓ1-norm, ℓp-norm and weighted ℓ1-norm. To verify the feasibility of the proposed benchmark, we compare the weighted ℓp-norm minimization against the three aforementioned norm minimization methods in sparse coding. Experimental results on image restoration applications, namely image inpainting and image compressive sensing recovery, demonstrate that the proposed scheme is feasible and outperforms many state-of-the-art methods.
Financial Management for Health-System Pharmacists, 2nd edition, serves as a guidebook to support the management of enterprise pharmacy finance across business and care continuums. The 2nd edition ...engages the reader with a mix of chapters, some new to this edition, along with a trove of new health-system pharmacy financial business cases. As leaders look to transform their organizations, the principles and practices provided give the reader the knowledge and guidance to craft a new path forward as they look to improve the provision of pharmacy and patient-care services.
This paper aims at solving the stochastic shortest path problem in vehicle routing, the objective of which is to determine an optimal path that maximizes the probability of arriving at the ...destination before a given deadline. To solve this problem, we propose a data-driven approach, which directly explores the big data generated in traffic. Specifically, we first reformulate the original shortest path problem as a cardinality minimization problem directly based on samples of travel time on each road link, which can be obtained from the GPS trajectory of vehicles. Then, we apply an ℓ 1 -norm minimization technique and its variants to solve the cardinality problem. Finally, we transform this problem into a mixed-integer linear programming problem, which can be solved using standard solvers. The proposed approach has three advantages over traditional methods. First, it can handle various or even unknown travel time probability distributions, while traditional stochastic routing methods can only work on specified probability distributions. Second, it does not rely on the assumption that travel time on different road segments is independent of each other, which is usually the case in traditional stochastic routing methods. Third, unlike other existing methods which require that deadlines must be larger than certain values, the proposed approach supports more flexible deadlines. We further analyze the influence of important parameters to the performances, i.e., accuracy and time complexity. Finally, we implement the proposed approach and evaluate its performance based on a real road network of Munich city. With real traffic data, the results show that it outperforms traditional methods.
PDF
