User anonsubmitter85 - MathOverflow

Dual Norm For Sum of 2-Norms

2012-07-02T18:22:38Z

What is the dual of a norm that is the sum of two-norms? Specifically, say we have the following norm for $\mathbf{x}\in \mathbb{R}^n$ and $\mathbf{A}_i \in \mathbb{R}^{m \times n}$

$\|\mathbf{x}\| = \displaystyle{ \sum_{i=0}^{k} \|\mathbf{A}_i \cdot \mathbf{x} \|_2}$ .

How would you then find

$\|\mathbf{y}\|_* = \underset{\mathbf{x}}{\mathrm{max}} \left\{ \mathbf{y}^T \mathbf{x} \;\; \mathrm{s.t.} \;\; \|\mathbf{x}\| \leq 1\right\}$ ?

I've tried solving for the convex conjugate looking for hints, but was unable to come up with anything meaningful.

Also, if anyone has recommendations for packages that I could use (preferably matlab-based) to solve the above numerically for systems as small as $10^3$ and as large as $10^6$, I'd greatly appreciate it. CVX, of which I am admittedly a novice and a hack, will not maximize convex functions.

Edit: So using the advice in the below comments, I end up with an eigen equation for the critical point $\mathbf{x}_*$:

$ \displaystyle{ \sum_{i=0}^{k} {\|\mathbf{A}_i \mathbf{x}_* \|_2 } } \cdot \mathbf{y} = \displaystyle{ \sum_{i=0}^{k} { {\mathbf{A}_i^T \mathbf{A_i} } \over{ \|\mathbf{A}_i \cdot \mathbf{x}_* \|_2 } } } \mathbf{x}_* \mathbf{x}_*^{T} \cdot \mathbf{y}$

The only other idea I have had is that we know that $\|y\|_*$ is the function such that $ \underset{\mathbf{x}}{\sup} \{ \mathbf{y}^T \mathbf{x} - \|\mathbf{x}\|\}$ is zero whenever $\|y\|_* \leq 1$ and is $\infty$ otherwise. I have not been able to use this in any meaningful way however.

Efficient Algorithm For Projection Onto A Convex Set

2012-06-26T01:17:32Z

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:

$\underset{\mathbf{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?

Comment by AnonSubmitter85

2012-07-21T20:36:44Z

I don't see how we know that $sum_{i}{\| A_i (x-\lambda_n d_n )\|} = \tau$ has a solution.

Comment by AnonSubmitter85

2012-07-04T01:33:35Z

Is this equivalent to what I put in the edit to my question?

Comment by AnonSubmitter85

2012-07-03T16:17:32Z

@Brain: I edited the question to use what you say is the standard definition, though I do not think it affects the answer.

Comment by AnonSubmitter85

2012-06-27T06:07:41Z

I am working with images, so each $n$ is the total number of pixels and there will be $n+p-1$ terms in the sum of norms, where $p$ will probably be less than 20 . I am currently trying to get a rough cut working, so I am using smaller images, say, $100 \times 100 \Rightarrow n = 10000$. However, I'd like to use more realistic image sizes, so $n$ could be over a million.

Comment by AnonSubmitter85

2012-06-26T10:38:13Z

@Suvrit: They don't have to be related but with what I am starting with they are. Currently, each $f_i$ and $g_i$ is a row from a 2-D convolution matrix (to be clear, matrices $F$ and $G$ represent two separate convolutions), so they are mostly permutations of one another. I have worked out an expression for the gradient and have been trying to get an unconstrained log-barrier implementation working to see how that performs, but have yet to get it working.

Comment by AnonSubmitter85

2012-06-26T02:04:02Z

@Vel Nias: I think you understand things correctly. However, in order to use either minConf_SPG() or minConf_SPG() I have to supply a projection function of the form: funProj(x) = argmin_y ||x - y||_2, subject to y is in X. Is this not the very problem I trying to solve? I am left looking at minConf thinking it is for problems for which my problem above is only a sub-problem.

Comment by AnonSubmitter85

2012-06-26T01:28:25Z

@Vel Nias: I looked at minConf but unless I have misread the page, it requires one to provide a function to compute the projection onto the convex set, which is the problem I am trying to find an efficient solution for.