| 摘要 |
Similarities between simplex projection with upper bounds and L1 projection are explored. Criteria for a-priori determination of sequence in which various constraints become active are derived, and this sequence is used to develop efficient algorithms for projecting a vector onto the L1-ball while observing box constraints. Three projection methods are presented. The first projection method performs exact projection in O(n2) worst case complexity, where n is the space dimension. Using a novel criteria for ordering constraints, the second projection method has a worst case complexity of O(n log n). The third projection method is a worst case linear time algorithm having O(n) complexity. The upper bounds defined for the projected entries guide the L1-ball projection to more meaningful predictions.
|
