Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given an elementwise nonnegative vector $y$, I'd like to find the projection of $y$ onto the simplex $S: \{ (x_1, \ldots, x_n) ~|~ \sum_{i=1}^n x_i=1, x_i \geq 0 \mbox{ for all } i \}$.

Is there a closed form expression for this? If not, I need to write a computer program which will compute this projection; is there something simple I could do to compute this?

Simplicity is more important to me than running time; I don't want to spend a long time coding this. I do realize this is a convex optimization problem and could be solved by using various optimization solvers, but that seems like overkill.

share|improve this question
    
Do you mean the projection from the origin? If so, the answer is simply $y/s$, where $s$ is the sum of the coordinates of $y$. –  Jim Belk Jun 18 '11 at 18:24
1  
@Jim Belk - I meant "projection" to mean the map which sends $y$ to the closest point to it in $S$. Sadly, this does not turn out to equal $y/s$. –  robinson Jun 18 '11 at 22:55
    
Related: math.stackexchange.com/questions/221546 –  Wok Oct 29 '12 at 12:43
    
Who were you robinson? What did you see? –  Wok Oct 29 '12 at 12:46

1 Answer 1

up vote 2 down vote accepted

You can try this article, or look at any book on Convex Opimization. The "closed formula" involves sorting, and you can find it using Lagrange multipliers (the version for inequality constraints).

share|improve this answer
    
This article is not available. –  Wok Oct 29 '12 at 12:43
    
Found. –  Wok Oct 29 '12 at 12:50
    
There is even a Matlab code. It is unfortunately not extensively vectorized, but it is simple to do so. –  Wok Oct 29 '12 at 14:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.