Timeline for Distance between two sets
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 8, 2014 at 16:08 | comment | added | Suvrit | @Math123: If your sets are polyhedral, then both Dykstra and alternating reflections may (in principle, but hard to quantify) converge at a linear rate, so you can "detect" when to stop. If your sets are "almost parallel" then both will slow down --- you have to experiment to see what convergence criterion works for you (in the worst case, to obtain an $\epsilon$-accurate solution, these methods may require $O(1/\epsilon)$ iterations, I think) | |
| Apr 8, 2014 at 16:05 | comment | added | Suvrit | @Igor: to my mind the greediness of AP can make it get "stuck" (e.g., at a corner). But more basically, AP just generates sequences that converges to a feasible point (because feasibility is what it set out to solve in the first place), there is nothing in the AP which should make it converge to the "best" feasible point (unless the set of feasible points in a singleton) --- a nice example is Example 11.24 in the book: "Convex analysis and monotone operator theory..." by Bauschke and Combettes. | |
| Apr 8, 2014 at 14:20 | comment | added | Math123 | @Suvrit, If I want to use Dykstra's projection algorithm for my problem then what could be the best criterion to get the best approximation for my problem? I mean under which criterion I can stop running the algorithm and get a good approximation for my points? | |
| Apr 8, 2014 at 14:09 | vote | accept | Math123 | ||
| Apr 7, 2014 at 19:38 | comment | added | Igor Rivin | Just out of curiosity: is there a standard reason/reference why the alternating projection method does not work? | |
| Apr 7, 2014 at 19:16 | vote | accept | Math123 | ||
| Apr 7, 2014 at 19:16 | |||||
| Apr 6, 2014 at 16:58 | comment | added | Suvrit | PS: Both Dykstra and Reflection methods rely on having access to a projection oracle for each of the convex sets. | |
| Apr 6, 2014 at 15:50 | history | answered | Suvrit | CC BY-SA 3.0 |