An $O(n\log(n))$ Algorithm for Projecting Onto the Ordered Weighted $\ell_1$ Norm Ball
The ordered weighted $\ell_1$ (OWL) norm is a newly developed generalization of the Octogonal Shrinkage and Clustering Algorithm for Regression (OSCAR) norm. This norm has desirable statistical properties and can be used to perform simultaneous clustering and regression. In this paper, we show how to compute the projection of an $n$-dimensional vector onto the OWL norm ball in $O(n\log(n))$ operations. In addition, we illustrate the performance of our algorithm on a synthetic regression test.
Code (0)
등록된 구현이 없습니다.
Tasks
ClusteringregressionSimilar Papers 제목 키워드 기반
k-Support and Ordered Weighted Sparsity for Overlapping Groups: Hardness and Algorithms
The k-support and OWL norms generalize the l1 norm, providing better prediction accuracy and better handling of correlated variables. We study the norms obtained from extending the k-support norm and OWL norms to the set…
The Ordered Weighted $\ell_1$ Norm: Atomic Formulation, Projections, and Algorithms
The ordered weighted $\ell_1$ norm (OWL) was recently proposed, with two different motivations: its good statistical properties as a sparsity promoting regularizer; the fact that it generalizes the so-called {\it octagon…
ClusteringregressionEfficient Projection Algorithms onto the Weighted l1 Ball
Projected gradient descent has been proved efficient in many optimization and machine learning problems. The weighted $\ell_1$ ball has been shown effective in sparse system identification and features selection. In this…
BIG-bench Machine Learningfeature selectionFrequency-weighted H2-optimal model order reduction via oblique projection
In projection-based model order reduction, a reduced-order approximation of the original full-order system is obtained by projecting it onto a reduced subspace that contains its dominant characteristics. The problem of f…
Computational EfficiencyAn Iteratively Reweighted Method for Sparse Optimization on Nonconvex $\ell_{p}$ Ball
This paper is intended to solve the nonconvex $\ell_{p}$-ball constrained nonlinear optimization problems. An iteratively reweighted method is proposed, which solves a sequence of weighted $\ell_{1}$-ball projection subp…