User anonsubmitter85 - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T21:46:00Z http://mathoverflow.net/feeds/user/24707 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms Dual Norm For Sum of 2-Norms AnonSubmitter85 2012-07-02T18:22:38Z 2012-07-04T07:02:45Z <p>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}$</p> <p><code>$\|\mathbf{x}\| = \displaystyle{ \sum_{i=0}^{k} \|\mathbf{A}_i \cdot \mathbf{x} \|_2}$</code>.</p> <p>How would you then find</p> <p><code>$\|\mathbf{y}\|_* = \underset{\mathbf{x}}{\mathrm{max}} \left\{ \mathbf{y}^T \mathbf{x} \;\; \mathrm{s.t.} \;\; \|\mathbf{x}\| \leq 1\right\}$</code>?</p> <p>I've tried solving for the convex conjugate looking for hints, but was unable to come up with anything meaningful.</p> <p>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.</p> <p>Edit: So using the advice in the below comments, I end up with an eigen equation for the critical point $\mathbf{x}_*$:</p> <p><code>$\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}$</code></p> <p>The only other idea I have had is that we know that <code>$\|y\|_*$</code> is the function such that <code>$\underset{\mathbf{x}}{\sup} \{ \mathbf{y}^T \mathbf{x} - \|\mathbf{x}\|\}$</code> is zero whenever <code>$\|y\|_* \leq 1$</code> and is $\infty$ otherwise. I have not been able to use this in any meaningful way however.</p> http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set Efficient Algorithm For Projection Onto A Convex Set AnonSubmitter85 2012-06-26T01:17:32Z 2012-06-26T17:25:57Z <p>Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:</p> <p><code>$\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$</code>,</p> <p>where $\mathbf{f}_i,\mathbf{g}_i \in \mathbb{R}^n$.</p> <p>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:</p> <p><code>$\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$</code>,</p> <p>where $\sigma_i$ is the operator norm of the $2 \times n$ matrix $[\mathbf{f}_i \;\; \mathbf{g}_i]^{\mathrm{T}}$.</p> <p>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?</p> http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set/100700#100700 Comment by AnonSubmitter85 AnonSubmitter85 2012-07-21T20:36:44Z 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. http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms/101244#101244 Comment by AnonSubmitter85 AnonSubmitter85 2012-07-04T01:33:35Z 2012-07-04T01:33:35Z Is this equivalent to what I put in the edit to my question? http://mathoverflow.net/questions/101168/dual-norm-for-sum-of-2-norms Comment by AnonSubmitter85 AnonSubmitter85 2012-07-03T16:17:32Z 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. http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set/100703#100703 Comment by AnonSubmitter85 AnonSubmitter85 2012-06-27T06:07:41Z 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. http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set Comment by AnonSubmitter85 AnonSubmitter85 2012-06-26T10:38:13Z 2012-06-26T10:38:13Z @Suvrit: They don't <i>have</i> 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. http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set Comment by AnonSubmitter85 AnonSubmitter85 2012-06-26T02:04:02Z 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. http://mathoverflow.net/questions/100652/efficient-algorithm-for-projection-onto-a-convex-set Comment by AnonSubmitter85 AnonSubmitter85 2012-06-26T01:28:25Z 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.