most recent 30 from http://mathoverflow.net 2013-05-20T01:36:33Z http://mathoverflow.net/feeds/user/2013 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/24215/optimization-over-permutation pacificmoth 2010-05-11T08:20:06Z 2010-11-27T23:22:13Z

<p>Say that we are given a set of variables, $X=\lbrace X_1,X_2,...,X_n \rbrace$. Their order $\Pi$ is an index array living in a permutation space $Perm(n)$. There is a positive function $f(X,\Pi) > 0$. I would like to optimize $f$ over $\Pi$, i.e., $\Pi^*=\arg\min_{\Pi\in Perm(n)}f(X,\Pi)$. Is there any good approximate algorithm for this?</p>

http://mathoverflow.net/questions/11183/how-can-i-embed-an-n-points-metric-space-to-a-hypercube-with-low-distortion pacificmoth 2010-01-08T20:41:00Z 2010-09-04T13:33:08Z

<p>I have a N-point metric space defined by the pairwise distance matrix. I want to encode these N points with binary strings, i.e. each point will be mapped to a vertex in a hypercube. The lengths of the edges on the hypercube could be different for different dimensions. The hypercube basically is a hyper-rectangle. Now the questions are the following: 1. Given the dimension of the hyper-rectangle, what is the lower bound of the distortion to the original metric space? 2. How to achieve that, i.e., the lengths of the edges, the vertices for each point? 3. Is the optimal embedding P or NP?</p> <p>$A = (P,C), |P| = N, C\in [0,1]^{N\times N}$, find a mapping $f:P \rightarrow \times_{j=1}^D $ { $0,l_j $ }, $l_j > 0$.</p> <p>such that for any $\frac{1}{\mu} C_{ij} \le |f(P_i)-f(P_j)| \le \mu C_{ij} $,</p> <p>where $\mu \sim \Omega(g(D,N))$, is a polynomial function. Thanks a lot!</p>

http://mathoverflow.net/questions/19326/how-to-estimate-a-polyhedronconvex-hull-classifier-from-data-sample pacificmoth 2010-03-25T16:24:05Z 2010-08-18T12:27:02Z

<p>Given a set of points $X\in\Re^D$, they have labels $Y\in${$-1,+1$}. I would like to separate the data labeled +1 and the data labeled -1 by a polyhedron. </p> <p>$min_w \sum_i \xi_i + \frac{1}{2}\|w\|_2^2$</p> <p>subject to: $ \xi_i > max_{j=1}^K[1-(w_j^Tx_i+b_j)]$, for $y_i=+1$</p> <p>and $ \xi_i > min_{j=1}^K[1+(w_j^Tx_i+b_j)]$, for $y_i=-1$ and $ \xi_i > 0 $, for all $i$.</p> <p>Where K is the number of faces of the polyhedron, i represents each sample, j represents each face of the polyhedron. I assume that all positive data go inside the polyhedron while negative data are outside. Following the max-margin principle, we let the distance of the point to the face offset by a margin 1.</p> <p>Optimizing with the first constraint is straightforward. But the second one seems difficult.</p> <p>Is there anyway to optimize them in a fast way to the optimal?</p>

http://mathoverflow.net/questions/22523/implicit-derivative pacificmoth 2010-04-25T19:06:27Z 2010-05-28T15:03:56Z

<p>If we have function $y=L(x_1,x_2,x_3,...,x_n)$, and function $z=R(x_1,x_2,x_3,...,x_n)$. How to compute the derivative $\frac{dy}{dz}$?</p> <p>Shall I do $\frac{dy}{dz} = \sup_{g\in \Re^n}\frac{\bigtriangledown_x L \cdot g}{\bigtriangledown_x R \cdot g}$?</p> <p>Is there any mathematical term associated with this kind of derivatives?</p>

http://mathoverflow.net/questions/22522/how-is-a-permutation-taken-as-an-equivalent-of-a-hash-function-in-minwise-indepen/22543#22543 pacificmoth 2010-04-25T22:45:01Z 2010-04-25T22:45:01Z

<p>The function could possibly be an index array of size n. For example, F[1,...,n] =[2,1,4,5...]. The total number of all these functions would be n!. The position of 1 implies the minimum hashed integer. For example, F[2] = 1 implies that 2 will be mapped into the minimum hash value (1). If we randomly choose F, it is easy to see that 1 appears in each position of the array equally likely. So the minwise independence condition holds. Hopefully this helps.</p>

http://mathoverflow.net/questions/6819/regression-problem-detect-outliers/11516#11516 pacificmoth 2010-01-12T09:45:28Z 2010-01-12T09:45:28Z

<p>To achieve the robust estimation, you could try the least square regression with L1 regularization that is also well-known LASSO algorithm. <a href="http://www-stat.stanford.edu/~tibs/lasso.html" rel="nofollow">http://www-stat.stanford.edu/~tibs/lasso.html</a> The relationship between robust estimation and lasso is explained in the following paper: <a href="http://www.cim.mcgill.ca/~xuhuan/papers/Lasso-NIPS.pdf" rel="nofollow">http://www.cim.mcgill.ca/~xuhuan/papers/Lasso-NIPS.pdf</a></p>

http://mathoverflow.net/questions/6449/searching-global-minima-fast pacificmoth 2009-11-22T09:46:27Z 2009-11-22T19:46:18Z

<p>I am minimizing a highly non-linear function. If I know the global minimum is at most some value, is this information helpful to design a faster algorithm than random restart?</p> <p> If we know an upper bound B so far, can we prove something like this, with a high probability, within M local minima visits, we will reach a local minimum B', and we have |B'-G| &lt; eta|B-G|, where G is the unknown global minimum. And M is some polynomial function of eta, and maybe the dimension of the solution space.</p>

http://mathoverflow.net/questions/24215/optimization-over-permutation pacificmoth 2010-05-12T19:53:54Z 2010-05-12T19:53:54Z

The function that I am looking at is more like a negative log joint probability coming from a Bayesian network. I wonder if there is any greedy algorithm could possibly give us somewhat non-trivial approximation. But the points you mentioned are pretty interesting.

http://mathoverflow.net/questions/22523/implicit-derivative/22526#22526 pacificmoth 2010-04-25T19:34:46Z 2010-04-25T19:34:46Z

Agree. The sup must lead to infinity if the two gradients are not parallel. Thanks.

http://mathoverflow.net/questions/22490/correlation-and-causation-when-can-we-believe-correlation-reasonably-at-least/22495#22495 pacificmoth 2010-04-25T18:54:18Z 2010-04-25T18:54:18Z

When you don't have knowledge about the causality, people go to statistics asking for help. Then it probably becomes a mathematical matter. Especially, to figure out the causality, we have to do &quot;actions&quot; and estimate the model from the intervened dataset instead of the original observed dataset. How to estimate the true distribution from the intervened data without any bias is an important mathematical task.

http://mathoverflow.net/questions/11183/how-can-i-embed-an-n-points-metric-space-to-a-hypercube-with-low-distortion/21322#21322 pacificmoth 2010-04-15T16:00:41Z 2010-04-15T16:00:41Z

randomized algorithm is already good enough. Thanks!

http://mathoverflow.net/questions/11183/how-can-i-embed-an-n-points-metric-space-to-a-hypercube-with-low-distortion/11193#11193 pacificmoth 2010-01-09T05:04:26Z 2010-01-09T05:04:26Z

If, by any chance, you find the ref, please do let me know. I kinda like the idea of converting l_1 to a hamming space by concatenation. Thanks.

http://mathoverflow.net/questions/11183/how-can-i-embed-an-n-points-metric-space-to-a-hypercube-with-low-distortion pacificmoth 2010-01-09T04:31:08Z 2010-01-09T04:31:08Z

Thanks for both of you. But my problem is that I don't really embed to a $\ell_1$ space. They have to be the vertices of the hyper-rectangle.

http://mathoverflow.net/questions/11183/how-can-i-embed-an-n-points-metric-space-to-a-hypercube-with-low-distortion/11193#11193 pacificmoth 2010-01-09T04:28:34Z 2010-01-09T04:28:34Z

This is a fairly educating answer. I appreciate it. But the thing here is that I have to restrict the assignment of points to the vertices instead of any vector inside the hypercube. So it isn't really embedding to $\ell_1$ space. Or, maybe you could show me how to move those points to the vertices after embedding without much distortion, that would be cool.

http://mathoverflow.net/questions/6449/searching-global-minima-fast/6461#6461 pacificmoth 2009-11-23T20:03:22Z 2009-11-23T20:03:22Z

Thanks again. Appreciate your input.

http://mathoverflow.net/questions/6449/searching-global-minima-fast/6461#6461 pacificmoth 2009-11-23T00:59:25Z 2009-11-23T00:59:25Z

Actually I am not sure what kind of prior information I should be checking. It is probably not invariant to solution space permutation (the NFL condition as you suggested). Maybe not sub-modular either. Do you have any suggestions on the properties that I should be looking for? On the other hand, I'm not looking for a polynomial global minimum solver. Instead, it would be good enough to me if any polynomial approximate solver can be improved, e.g. from N&lt;sup&gt;2&lt;/sup&gt; to N logN, when the upper bound information or any prior information provided.

http://mathoverflow.net/questions/6449/searching-global-minima-fast/6461#6461 pacificmoth 2009-11-22T19:40:01Z 2009-11-22T19:40:01Z

Thanks Martin. If we know an upper bound B so far, can we prove something like this, with a high probability, within M local minima visits, we will reach a local minimum B', and we have |B'-G| &lt; eta|B-G|, where G is the unknown global minimum. And M is some polynomial function of eta, and maybe the dimension of the solution space.