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 $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:

$\underset{p}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; \mathrm{s.t.} \;\; \displaystyle \sum_{i}{ \left \| \left [ \begin{array}{c} \mathbf{f}_i^\mathrm{T} \\ \mathbf{g}_i^\mathrm{T} \end{array} \right] \cdot \mathbf{p} \right \|_2 } \leq \tau $,

where $\mathbf{f}_i,\mathbf{g}_i \in \mathbb{R}^n$.

The above is a convex function over a convex set and as such should have a unique solution. Moreover, we can find the upper bound on the summation as follows:

$\displaystyle \sum_{i}{ \left \| \left [ \begin{array}{c} \mathbf{f}_i^\mathrm{T} \\ \mathbf{g}_i^\mathrm{T} \end{array} \right] \cdot \mathbf{p} \right \|_2 } \leq \|\mathbf{p}\|_2 \cdot \sum_i \sigma_i $,

where $\sigma_i$ is the operator norm of the $2 \times n$ matrix $[\mathbf{f}_i \;\; \mathbf{g}_i]^{\mathrm{T}}$.

I have been using CVX to solve the above, but it's just too slow in its current form. I have not figured out how to make use of them, but the operator norms are easily found before-hand. Can anyone suggest a re-formulation of the above or an algorithm that is tailored to these types of problems?

share|improve this question
    
Can't you use Lagrange multiplier method and solve? –  Ashok Jun 26 '12 at 5:10
    
@Ashok: I have to admit that I do not see how to do that. –  AnonSubmitter85 Jun 26 '12 at 5:25

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.