The Experts below are selected from a list of 999 Experts worldwide ranked by ideXlab platform
Yuping Wang - One of the best experts on this subject based on the ideXlab platform.
-
a sufficient condition on monotonic increase of the number of Nonzero Entry in the optimizer of l1 norm penalized least square problem
arXiv: Machine Learning, 2011Co-Authors: Junbo Duan, Charles Soussen, David Brie, Yuping WangAbstract:The $\ell$-1 norm based optimization is widely used in signal processing, especially in recent compressed sensing theory. This paper studies the solution path of the $\ell$-1 norm penalized least-square problem, whose constrained form is known as Least Absolute Shrinkage and Selection Operator (LASSO). A solution path is the set of all the optimizers with respect to the evolution of the hyperparameter (Lagrange multiplier). The study of the solution path is of great significance in viewing and understanding the profile of the tradeoff between the approximation and regularization terms. If the solution path of a given problem is known, it can help us to find the optimal hyperparameter under a given criterion such as the Akaike Information Criterion. In this paper we present a sufficient condition on $\ell$-1 norm penalized least-square problem. Under this sufficient condition, the number of Nonzero entries in the optimizer or solution vector increases monotonically when the hyperparameter decreases. We also generalize the result to the often used total variation case, where the $\ell$-1 norm is taken over the first order derivative of the solution vector. We prove that the proposed condition has intrinsic connections with the condition given by Donoho, et al \cite{Donoho08} and the positive cone condition by Efron {\it el al} \cite{Efron04}. However, the proposed condition does not need to assume the sparsity level of the signal as required by Donoho et al's condition, and is easier to verify than Efron, et al's positive cone condition when being used for practical applications.
Einar Steingrímsson - One of the best experts on this subject based on the ideXlab platform.
-
Enumerating (2+2)-free posets by indistinguishable elements
arXiv: Combinatorics, 2010Co-Authors: Mark Dukes, Sergey Kitaev, Jeffrey B. Remmel, Einar SteingrímssonAbstract:A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. Two elements in a poset are indistinguishable if they have the same strict up-set and the same strict down-set. Being indistinguishable defines an equivalence relation on the elements of the poset. We introduce the statistic maxindist, the maximum size of a set of indistinguishable elements. We show that, under a bijection of Bousquet-Melou et al., indistinguishable elements correspond to letters that belong to the same run in the so-called ascent sequence corresponding to the poset. We derive the generating function for the number of (2+2)-free posets with respect to both maxindist and the number of different strict down-sets of elements in the poset. Moreover, we show that (2+2)-free posets P with maxindist(P) at most k are in bijection with upper triangular matrices of nonnegative integers not exceeding k, where each row and each column contains a Nonzero Entry. (Here we consider isomorphic posets to be equal.) In particular, (2+2)-free posets P on n elements with maxindist(P)=1 correspond to upper triangular binary matrices where each row and column contains a Nonzero Entry, and whose entries sum to n. We derive a generating function counting such matrices, which confirms a conjecture of Jovovic, and we refine the generating function to count upper triangular matrices consisting of nonnegative integers not exceeding k and having a Nonzero Entry in each row and column. That refined generating function also enumerates (2+2)-free posets according to maxindist. Finally, we link our enumerative results to certain restricted permutations and matrices.
Steingrimsson Einar - One of the best experts on this subject based on the ideXlab platform.
-
Enumerating (2+2)-free posets by indistinguishable elements
2011Co-Authors: Dukes Mark, Kitaev Sergey, Remmel Jeffrey, Steingrimsson EinarAbstract:A poset is said to be (2+2)-free if it does not contain an induced subposet that is isomorphic to 2+2, the union of two disjoint 2-element chains. Two elements in a poset are indistinguishable if they have the same strict up-set and the same strict down-set. Being indistinguishable defines an equivalence relation on the elements of the poset. We introduce the statistic maxindist, the maximum size of a set of indistinguishable elements. We show that, under a bijection of Bousquet-Melou et al., indistinguishable elements correspond to letters that belong to the same run in the so-called ascent sequence corresponding to the poset. We derive the generating function for the number of (2+2)-free posets with respect to both maxindist and the number of different strict down-sets of elements in the poset. Moreover, we show that (2+2)-free posets P with maxindist(P) at most k are in bijection with upper triangular matrices of nonnegative integers not exceeding k, where each row and each column contains a Nonzero Entry. (Here we consider isomorphic posets to be equal.) In particular, (2+2)-free posets P on n elements with maxindist(P)=1 correspond to upper triangular binary matrices where each row and column contains a Nonzero Entry, and whose entries sum to n. We derive a generating function counting such matrices, which confirms a conjecture of Jovovic, and we refine the generating function to count upper triangular matrices consisting of nonnegative integers not exceeding k and having a Nonzero Entry in each row and column. That refined generating function also enumerates (2+2)-free posets according to maxindist. Finally, we link our enumerative results to certain restricted permutations and matrices.Comment: 16 page
Junbo Duan - One of the best experts on this subject based on the ideXlab platform.
-
a sufficient condition on monotonic increase of the number of Nonzero Entry in the optimizer of l1 norm penalized least square problem
arXiv: Machine Learning, 2011Co-Authors: Junbo Duan, Charles Soussen, David Brie, Yuping WangAbstract:The $\ell$-1 norm based optimization is widely used in signal processing, especially in recent compressed sensing theory. This paper studies the solution path of the $\ell$-1 norm penalized least-square problem, whose constrained form is known as Least Absolute Shrinkage and Selection Operator (LASSO). A solution path is the set of all the optimizers with respect to the evolution of the hyperparameter (Lagrange multiplier). The study of the solution path is of great significance in viewing and understanding the profile of the tradeoff between the approximation and regularization terms. If the solution path of a given problem is known, it can help us to find the optimal hyperparameter under a given criterion such as the Akaike Information Criterion. In this paper we present a sufficient condition on $\ell$-1 norm penalized least-square problem. Under this sufficient condition, the number of Nonzero entries in the optimizer or solution vector increases monotonically when the hyperparameter decreases. We also generalize the result to the often used total variation case, where the $\ell$-1 norm is taken over the first order derivative of the solution vector. We prove that the proposed condition has intrinsic connections with the condition given by Donoho, et al \cite{Donoho08} and the positive cone condition by Efron {\it el al} \cite{Efron04}. However, the proposed condition does not need to assume the sparsity level of the signal as required by Donoho et al's condition, and is easier to verify than Efron, et al's positive cone condition when being used for practical applications.
Sina Jafarpour - One of the best experts on this subject based on the ideXlab platform.
-
Revisiting Model Selection and Recovery of Sparse Signals Using One-Step Thresholding
2013Co-Authors: Waheed U. Bajwa, Robert Calderbank, Sina JafarpourAbstract:Abstract—This paper studies non-asymptotic model selection and recovery of sparse signals in high-dimensional, linear inference problems. In contrast to the existing literature, the focus here is on the general case of arbitrary design matrices and arbitrary Nonzero entries of the signal. In this regard, it utilizes two easily computable measures of coherence—termed as the worstcase coherence and the average coherence—among the columns of a design matrix to analyze a simple, model-order agnostic one-step thresholding (OST) algorithm. In particular, the paper establishes that if the design matrix has reasonably small worstcase and average coherence then OST performs near-optimal model selection when either (i) the energy of any Nonzero Entry of the signal is close to the average signal energy per Nonzero Entry or (ii) the signal-to-noise ratio (SNR) in the measurement system is not too high. Further, the paper shows that if the design matrix in addition has sufficiently small spectral norm then OST also exactly recovers most sparse signals whose Nonzero entries have approximately the same magnitude even if the number of Nonzero entries scales almost linearly with the number of rows of the design matrix. Finally, the paper also presents various classes of random and deterministic design matrices that can be used together with OST to successfully carry out near-optimal model selection and recovery of sparse signals under certain SNR regimes or for certain classes of signals. I
-
why gabor frames two fundamental measures of coherence and their role in model selection
Journal of Communications and Networks, 2010Co-Authors: Waheed U. Bajwa, Robert Calderbank, Sina JafarpourAbstract:The problem of model selection arises in a number of contexts, such as subset selection in linear regression, estimation of structures in graphical models, and signal denoising. This paper studies non-asymptotic model selection for the general case of arbitrary (random or deterministic) design matrices and arbitrary Nonzero entries of the signal. In this regard, it generalizes the notion of incoherence in the existing literature on model selection and introduces two fundamental measures of coherence — termed as the worst-case coherence and the average coherence — among the columns of a design matrix. It utilizes these two measures of coherence to provide an in-depth analysis of a simple, model-order agnostic one-step thresholding (OST) algorithm for model selection and proves that OST is feasible for exact as well as partial model selection as long as the design matrix obeys an easily verifiable property, which is termed as the coherence property. One of the key insights offered by the ensuing analysis in this regard is that OST can successfully carry out model selection even when methods based on convex optimization such as the lasso fail due to the rank deficiency of the submatrices of the design matrix. In addition, the paper establishes that if the design matrix has reasonably small worst-case and average coherence then OST performs near-optimally when either (i) the energy of any Nonzero Entry of the signal is close to the average signal energy per Nonzero Entry or (ii) the signal-to-noise ratio in the measurement system is not too high. Finally, two other key contributions of the paper are that (i) it provides bounds on the average coherence of Gaussian matrices and Gabor frames, and (ii) it extends the results on model selection using OST to low-complexity, model-order agnostic recovery of sparse signals with arbitrary Nonzero entries. In particular, this part of the analysis in the paper implies that an Alltop Gabor frame together with OST can successfully carry out model selection and recovery of sparse signals irrespective of the phases of the Nonzero entries even if the number of Nonzero entries scales almost linearly with the number of rows of the Alltop Gabor frame.
