User rcompton - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:32:32Z http://mathoverflow.net/feeds/user/6360 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/121364/fixed-point-theorem-on-graphs Fixed point theorem on graphs? rcompton 2013-02-09T22:46:09Z 2013-02-11T02:52:54Z <p>Originally posted here: <a href="http://math.stackexchange.com/questions/276167/fixed-point-theorem-on-graphs" rel="nofollow">http://math.stackexchange.com/questions/276167/fixed-point-theorem-on-graphs</a></p> <p>--</p> <p>I have a graph $G=(V,E)$ where to each vertex $v$ I have associated a value, $\hat{v}$ (ie I have a "network" in the terminology here <a href="http://snap.stanford.edu/snap/index.html" rel="nofollow">http://snap.stanford.edu/snap/index.html</a> ).</p> <p>Let $\phi : \hat{V} \rightarrow \hat{V}$ be the function which takes the value associated to each node and replaces it with median of the values of the adjacent nodes.</p> <p>Empirically, iterating $\phi$ converges. Why?</p> <p><strong>edit</strong>: The graph is large and follows this model: <a href="http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model" rel="nofollow">http://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model</a> . Also, for ~1% of nodes, $\phi$ is the identity. There is some related work here: <a href="http://www.cs.cmu.edu/~zhuxj/pub/CMU-CALD-02-107.pdf" rel="nofollow">http://www.cs.cmu.edu/~zhuxj/pub/CMU-CALD-02-107.pdf</a></p> <p><strong>edit</strong>: Looks like I can just replace the $P(j \rightarrow i)$ in the label propagation paper with $P(j \rightarrow i) = 1\; if \; \text{j is the median, }0 \text{ else}$, then I can copy their convergence result.</p> <p><strong>edit</strong>: Wait, no. If I do that then P changes each step so it's not a direct copy...</p> http://mathoverflow.net/questions/106705/2d-problems-which-are-easier-to-solve-in-3d/106707#106707 Answer by rcompton for 2D Problems Which are Easier to Solve in 3D rcompton 2012-09-09T04:44:19Z 2012-09-09T04:55:23Z <p>This is essentially the idea behind level set methods (cf <a href="http://en.wikipedia.org/wiki/Level_set_method" rel="nofollow">http://en.wikipedia.org/wiki/Level_set_method</a> ).</p> <p>There are several situations where one needs to study the behavior of a dynamic surface with complicated topology. In fire simulation, one needs to track the motion of an air/fuel interface which is often not connected. In image segmentation, one needs to move the boundary between inner/outer regions until a steady state is reached. In fluid mechanics, breaking waves detach from the main body of water.</p> <p>Solving differential equations on surfaces with complicated topology is difficult numerically. It turns out that when one represents these surfaces as level sets of a higher dimensional function these connectivity problems disappear and higher quality simulations are possible.</p> http://mathoverflow.net/questions/105276/quantifying-the-amount-of-structure-in-a-data-set-via-random-matrix-theory Quantifying the amount of structure in a data set via random matrix theory rcompton 2012-08-22T23:16:35Z 2012-08-22T23:16:35Z <p>Given a data matrix, $M \in \mathbb{R}^{n \times p}$, I am interested in methods quantifying the amount of structure in present in $M$.</p> <p>I've found a few approaches, but I would like to learn more about what is available and what can be done given new developments in random matrix theory. I understand that the phrase "quantifying the amount of structure" is quite vague, any references that can clear that up would be appreciated.</p> <p>Currently, I know about the following methods:</p> <p>-- Compare the leading singular value of $M$ against the leading singular value of a shuffled version of $M$ (cf. <a href="http://www.plosgenetics.org/article/info:doi/10.1371/journal.pgen.0030160" rel="nofollow">http://www.plosgenetics.org/article/info:doi/10.1371/journal.pgen.0030160</a>).</p> <p>Here, one determines whether or not $M$ has structure by comparing the leading singular value of $M$, $\sigma_{max}(M)$, with the leading singular value of a matrix, $\tilde{M}$, obtained by permuting the entries of $M$. If $| \sigma_{max}(M) - \sigma_{max}(\tilde{M}) | / \sigma_{max}(M) &lt; 0.15$ then $M$ is said to contain no structure. Otherwise, the leading rank-1 approximation to $M$ is subtracted off and the process is repeated until no structure remains.</p> <p>-- Compare the leading singular value of $M$ against the Tracy-Widom distribution (cf. <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1009210544" rel="nofollow">http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aos/1009210544</a> and <a href="http://www.plosgenetics.org/article/info:doi/10.1371/journal.pgen.0020190" rel="nofollow">http://www.plosgenetics.org/article/info:doi/10.1371/journal.pgen.0020190</a> )</p> <p>This is identical to the previous test with the exception that we test against the Tracy-Widom distribution rather than the singular values of a shuffled version of $M$. I suppose this test is more rigorous but will only tell whether or not the entries of $M$ are Gaussian ( though I get the impression that newer results improve on this, eg <a href="http://arxiv.org/pdf/0906.0510v10.pdf" rel="nofollow">http://arxiv.org/pdf/0906.0510v10.pdf</a> ).</p> <p>-- Check how well the correlation eigenvalues of $M$ agree with the semicircular law (cf. <a href="http://arxiv.org/pdf/cond-mat/0108023v1.pdf" rel="nofollow">http://arxiv.org/pdf/cond-mat/0108023v1.pdf</a> )</p> <p>Here, the authors study the structure of several time series by observing how many eigenvalues lie within Wigner's semicircle. It would be nice if the number of significant principle components one gets from the methods above is equal to the number of eigenvalues which lie outside the semicircle. I have no idea if this is true.</p> http://mathoverflow.net/questions/98698/convolutive-noise-removal Convolutive noise removal rcompton 2012-06-03T03:30:43Z 2012-06-06T08:21:03Z <p>I have the time domain signal $$u_o(t) = u(t)e^{-t/\tau}\eta(t) + \sigma(t)$$ where $\tau$ is known, $\eta$ is non-Gaussian noise, and $\sigma$ is Gaussian noise. The distribution of $\eta(t)$ is known, but only numerically. I also have prior knowledge that $u(t)$ is a sum of a small number of sinusoids. How can I recover $u(t)$ from $u_o(t)$?</p> <p>In the case where $\eta$ is not present, I can Fourier transform to obtain: $$\hat{u}_o(\xi) = \hat{u}(\xi)*l(\xi) + \sigma(\xi)$$ where $l$ is a Lorentzian. The deconvolution is easy to solve with basis pursuit: $$argmin |u|_1 \; subject \; to \; \|l*u - \hat{u_o} \|^2 \leq \mu$$ This ignores $\eta$ as well as our statistical knowledge of $\eta$. Are there ideas on how I can incorporate $\eta$ into my denoising model? Is there a different model I should look into?</p> <p>edit: looks like I need to set up a MAP estimate for $f = u*\eta + \sigma$. I think I can sort it out when it's just $\eta$ or just $\sigma$.</p> http://mathoverflow.net/questions/87303/best-algorithm-software-for-solving-a-planar-transportation-problem/92632#92632 Answer by rcompton for Best algorithm/software for solving a planar transportation problem ? rcompton 2012-03-30T00:16:44Z 2012-03-30T00:29:37Z <p>How much have you looked into the theory of optimal transport? It's very popular for image warping/registration.</p> <p>There's codes available to compute the $l1$-optimal transport distance (also referred to as "Earth mover's distance") here: <a href="http://ai.stanford.edu/~rubner/emd/default.htm" rel="nofollow">http://ai.stanford.edu/~rubner/emd/default.htm</a> and here: <a href="http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/" rel="nofollow">http://www.cs.huji.ac.il/~ofirpele/FastEMD/code/</a></p> <p>The $l2$ optimal mass transport problem is quite difficult but can be solved: <a href="http://www.springerlink.com/index/40PGJBKDC9V0UH94.pdf" rel="nofollow">http://www.springerlink.com/index/40PGJBKDC9V0UH94.pdf</a> </p> <p>Once it's possible to compute the cost to get between two distributions of points I guess you'll have to optimize to see which distribution is closest to the one you have. Maybe something like: $$\min_\rho d(\rho_0, \rho)\;subject\;to\;\rho \leq c, \rho \geq 0,\int \rho = 1$$ where $\rho$ is a probability distribution describing the density of points and $c$ is your threshold. Maybe you can do this with a Lagrange multiplier and gradient descent?</p> http://mathoverflow.net/questions/88171/efficiently-computing-a-few-localized-eigenvectors Efficiently computing a few localized eigenvectors rcompton 2012-02-11T02:18:54Z 2012-02-23T10:15:48Z <p>Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$.</p> <p>The lowest 1000 eigenfunctions of $H$, $\psi_i$, can be partitioned using a region, $\Omega \subset \mathbb{R}^2$, such that each $\psi_i$ localizes either inside of $\Omega$ or outside of $\Omega$. $\Omega$ is not a subspace of $\mathbb{R}^2$ as it may be an oddly shaped region.</p> <p>Label the inner eigenfunctions $\psi_i^{in}$ and the outer ones $\psi_i^{out}$. There's only about 10 $\psi_i^{in}$s. Given $\Omega$, my goal is to efficiently compute the $\psi_i^{in}$.</p> <p>One way to find the $\psi_i^{in}$ would be to discretize, compute all 1000 $\psi_i$s, and then partition. This is what I do now (5-point stencil for $\triangle$ on a $10^3 \times 10^3$ grid). The problem is that this requires diagonalizing over a 1000 dimensional space in order to get 10 eigenvectors. It seems like there would be a cheaper way to compute the $\psi_i^{in}$.</p> <p><strong>Edit:</strong> I reposted to <a href="http://scicomp.stackexchange.com/questions/1396/efficiently-computing-a-few-localized-eigenvectors#comment2200_1396" rel="nofollow">http://scicomp.stackexchange.com/questions/1396/efficiently-computing-a-few-localized-eigenvectors#comment2200_1396</a> and hopefully clarified the problem statement.</p> <p><strong>Edit</strong> I think I can solve this if I can at least figure a way to solve $$\max \psi^T H \psi \text{ subject to } P\psi = \psi \text{ and } \psi^T \psi = 1$$ where $P$ is projection onto the space of functions localized over $\Omega$. My guess is that this will end up looking like power iterations with a projection step built in between matrix applies. If this is doable then something like inverse iteration should be doable which will give me what I want.</p> http://mathoverflow.net/questions/79290/how-to-do-mgram-schmidt-orthogonalization-with-integers-real-life-problem/80343#80343 Answer by rcompton for How to do (m)Gram-Schmidt orthogonalization with integers ? (real life problem) ("mathematicalized reformulation") rcompton 2011-11-07T23:31:58Z 2011-11-07T23:31:58Z <p>Well, if your microprocessors can handle fixed point arithmetic then here is a matlab commercial that should do it: <a href="http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html" rel="nofollow">http://www.mathworks.com/products/fixed/demos.html?file=/products/demos/shipping/fixedpoint/cordicqr_demo.html</a></p> <p>Gram-Schmidt is not numerically stable even when you can use floating point so my guess is that you will have many problems if you stay that course.</p> http://mathoverflow.net/questions/75917/definition-of-spectral-gradient Definition of spectral gradient rcompton 2011-09-20T07:14:56Z 2011-09-21T05:48:26Z <p>Consider this differential operator $$\mathcal{H}(\phi(\mathbf{x})) = -\triangle + V(\mathbf{x})H_\epsilon (\phi(\mathbf{x}))$$ where $\mathbf{x} \in \mathbb{R}^2$, $\phi : \mathbb{R}^2 \rightarrow \mathbb{R}^2$, and $H_\epsilon$ is a relaxed version of the Heaviside step function.</p> <p>I am interested in studying spectra of $\mathcal{H}$ as $\phi$ varies but am not sure about the definitions. Suppose $(v,\lambda)$ is an eigenpair of $\mathcal{H}$, I want to know $\nabla v$ and $\nabla \lambda$.</p> <p>For example, I compute $\nabla \lambda$ as $$\mathcal{H}v = \lambda v$$ $$\implies \nabla (\mathcal{H}v) = \nabla (\lambda v)$$ $$\implies \nabla \mathcal{H} v + \mathcal{H} \nabla v = \nabla \lambda v + \lambda \nabla v$$ $$\implies \nabla \lambda = v^T \nabla \mathcal{H} v$$ $$\implies \nabla \lambda = v^T V(\mathbf{x}) \delta_\epsilon(\phi(\mathbf{x})) v$$</p> <p>which is weird since $\nabla \lambda$ is a number and I don't know that I computed $\nabla \mathcal{H}$ properly. It's the same way Terry does the computation in the single variable case (cf <a href="http://terrytao.wordpress.com/2008/10/28/when-are-eigenvalues-stable/" rel="nofollow">http://terrytao.wordpress.com/2008/10/28/when-are-eigenvalues-stable/</a> ).</p> <p>Any advice? I hope to use $\phi$ in a level set method for domain decomposition.</p> <p>Edit: Restrict everything to the discrete case (ie $\mathcal{H}$ is a matrix, like in the link above) and I still don't know how to do this. I guess the concise way to state my question is "Given a matrix $\mathcal{H}(\phi)$ does anyone know a formula for the first variation of the eigenvalues or eigenvectors of $\mathcal{H}$?"</p> http://mathoverflow.net/questions/75338/eigenfunctions-of-random-graphs/75919#75919 Answer by rcompton for Eigenfunctions of random graphs rcompton 2011-09-20T07:38:57Z 2011-09-20T07:38:57Z <p>Laplacian eigenvectors tend to localize over nodes with similar degrees. Some illustrations and exposition begin on page two in this paper: doi:10.1038/nphys1651 with a more detailed explanation here: 10.1103/PhysRevE.77.031102</p> http://mathoverflow.net/questions/53571/operator-compression-preserving-lowest-energy-eigenspace Operator compression preserving lowest energy eigenspace. rcompton 2011-01-28T06:02:57Z 2011-05-05T21:14:48Z <p>I have a large ($10^6$ by $10^6$) sparse ($0.4$% nonzero) hermitian matrix $H$ arising from the discretization of an elliptic PDE. I would like to approximate $H$ with a smaller matrix $H'$ in such a way that $H'$ and $H$ have nearly identical eigenvectors and eigenvalues for the lowest 5 or 6 eigenvalues.</p> <p>This could be done if I knew the lowest eigenvectors of $H$ as I could simply restrict $H$ to the space spanned by these values. However I would like to be able to find an approximation before solving eigenvalue problem (in fact my eventual goal is to make solving the eigenvalue problem more efficient).</p> <p>I know of the recent work on approximating SDD systems with graph sparsification as well as multilevel operator compression. What else is out there?</p> <p>The application is a full-CI treatment of a multiparticle quantum system.</p> http://mathoverflow.net/questions/59939/identifying-poisoned-wines/60340#60340 Answer by rcompton for Identifying poisoned wines rcompton 2011-04-02T02:49:24Z 2011-04-02T02:49:24Z <p>There's a very similar problem in compressed sensing genetic screening for rare alleles (cf <a href="http://nar.oxfordjournals.org/content/38/19/e179.full" rel="nofollow">http://nar.oxfordjournals.org/content/38/19/e179.full</a> ). The technique almost works here provided we can determine how much poison a rat gets. Seems reasonable, a rat that gets more poison dies faster.</p> <p>In our problem the idea would be to create a sample for each rat to drink by randomly pooling together wine from many bottles. Specifically, for rat $i$ we draw $A_{ij}$ liters of wine from each of the $j=1,...,N$ bottles where $A_{ij}$ is $\mathcal{N}(0,1)$ distributed. Let $b_i$ denote the amount of poison measured in rat $i$ and let $x_j$ denote the amount of poison in bottle $j$.</p> <p>This yields the highly underdetermined linear system $$A\vec{x} = \vec{b}$$ where we know a priori that $\vec{x}$ is sparse. The sparsest solution to this linear system may obtained in polynomial time by solving the convex optimization $$\min |\vec{x}|_1 \text{ s.t. } A\vec{x}=\vec{b}$$</p> <p>The number of rats required here is $\mathcal{O}(s \log(N))$ where $s$ is the number of poison bottles.</p> http://mathoverflow.net/questions/57715/remap-fft-frequency-bin-distribution/58118#58118 Answer by rcompton for Remap FFT frequency bin distribution rcompton 2011-03-11T00:31:21Z 2011-03-11T00:31:21Z <p>Pick a large number of points to discretize the frequency domain with. When you have a time signal with less points zero pad until you hit that number. This is sometimes called "spectral interpolation" <a href="https://ccrma.stanford.edu/~jos/st/Zero_Padding_Theorem_Spectral.html" rel="nofollow">https://ccrma.stanford.edu/~jos/st/Zero_Padding_Theorem_Spectral.html</a> and does a nice job of interpreting the frequency domain.</p> http://mathoverflow.net/questions/48366/laplace-equation-with-mixed-boundary-conditions/48432#48432 Answer by rcompton for Laplace equation with mixed boundary conditions rcompton 2010-12-06T12:06:44Z 2010-12-06T12:06:44Z <p>The solution to the Dirichlet problem is unique by the maximum principle. For the same reason, the solution to the Neumann problem is unique up to a constant.</p> <p>At worst your problem would fail uniqueness by a constant, but those Dirichlet conditions you've got will prevent this.</p> <p>This carries over to the discrete case. But note that the discrete case is an easier problem since you can just write out the matrix you need to invert and check if it's invertible.</p> http://mathoverflow.net/questions/48122/the-convergence-of-jacobi-and-gauss-seidel-iteration/48125#48125 Answer by rcompton for The Convergence of Jacobi and Gauss-Seidel Iteration rcompton 2010-12-03T02:51:34Z 2010-12-03T02:51:34Z <p>You need to be careful how you define rate of convergence. For Gauss-Seidel and Jacobi you split $A$ and rearrange \begin{eqnarray} Ax &amp;=&amp; b\ M-K &amp;=&amp; b \ \implies x &amp;=&amp; M^{-1}Kx + M^{-1}b\ &amp;\def&amp;Rx + c \end{eqnarray} Giving the iteration $x_{m+1} = Rx_m + c$. We (Demmel's book) define the rate of convergence as the increase in the number of correct decimal places per iteration $$r = -\log_{10}( \rho(R))$$ where $\rho(R)$ is the spectral radius of $R$. It can be shown that for $A$ strictly row diagonally dominant that $$\rho(R_{\text{Gauss}}) \leq \rho(R_{\text{Jacobi}}) &lt; 1$$ indicating that the rate of convergence for Gauss Seidel is greater than that of Jacobi.</p> <p>However I have never seen a significant difference in speed between the two methods.</p> http://mathoverflow.net/questions/47871/suggestions-for-sonifying-math/47977#47977 Answer by rcompton for Suggestions for sonifying math rcompton 2010-12-02T01:39:38Z 2010-12-02T01:39:38Z <p>I messed around with this when I was a C++ TA. I came up with "musical sorting algorithms", "musical Gauss Seidel" and a terrible sounding FFT. Details: <a href="http://www.math.ucla.edu/~rcompton/art.html" rel="nofollow">http://www.math.ucla.edu/~rcompton/art.html</a></p> http://mathoverflow.net/questions/45119/schrodingers-equation-over-a-randomized-grid Schrodinger's equation over a randomized grid rcompton 2010-11-06T23:26:33Z 2010-11-15T07:21:22Z <p>I am interested in solutions to $$\frac{d}{dt} \Psi = -iH \Psi$$ for $H$ hermitian and time independent. This boils down to evaluating $$\Psi(t) = e^{-iHt}\Psi_0$$ at points of interest $t_n$. I want to quickly compute $\Psi(t)$ up to a large final time $T$ by spacing the $t_n$ randomly and advancing the propagator over the nonuniform grid.</p> <p>To be specific, fix $\Delta t$ and draw $t_n$ uniformly at random from $\Delta t, 2\Delta t, ..., N\Delta t$. The gaps $t_{n+1}-t_{n}$ will be distributed geometrically (ie we will have large gaps).</p> <p>Any ideas how I could compute $e^{-iHt}$ accurately and efficiently when $t$ may be large?</p> <p>Fast approximations that I know of (eg Strang splitting, Trotter product) are very efficient but I have found them to be horribly inaccurate and unstable for large gaps.</p> <p>Machine precision accuracy is achieved by expanding $e^{-iHt}$ in Chebyshev polynomials, but the computational cost (measured by counting applications of $H$) scales linearly with the timestep size and we get to $T$ no faster.</p> <p>I am beginning to think that spectrally accurate approximations of $e^{-iHt}$ provably require linearly more applications of $H$ as $T$ increases. Does anyone know if this is proven?</p> <p>Thanks for solving my thesis problem,</p> <p>Ryan</p> http://mathoverflow.net/questions/35987/multivariate-bisection/40703#40703 Answer by rcompton for Multivariate Bisection rcompton 2010-10-01T02:37:38Z 2010-10-01T02:37:38Z <p>You might want to consider the vector field</p> <p>$\vec{F}(x,y) = (f(x,y), g(x,y))$</p> <p>and look for sources and sinks of $\vec{F}$. I think this could be done by recursively dividing up the plane into squares and calculating the winding number of each square. If it is nonzero then you have a critical point within that square (cf Thm 2 <a href="http://www.mpi-inf.mpg.de/~ag4-gm/handouts/06gm_top3.pdf" rel="nofollow">this paper</a>) and should divide further.</p> http://mathoverflow.net/questions/36914/is-any-bias-introduced-from-initial-clustering/36948#36948 Answer by rcompton for Is any bias introduced from initial clustering rcompton 2010-08-28T00:57:09Z 2010-08-28T00:57:09Z <p>I've looked at this for PCA-based clustering.</p> <p><img src="http://i.imgur.com/Ov6DW.jpg" alt="alt text"></p> <p>Here is some PC clustering of a simulated dataset. We first draw the clusters as red xs on PCs computed from the entire dataset. A few random points (these are marked blue) are removed from the dataset and the PCs are computed on reduced data. The blue data are then plotted against the reduced PCs and colored green.</p> <p><img src="http://i.imgur.com/GSzNt.jpg" alt="alt text"></p> <p>I don't have a rigorous bound (I would really like some references) but from what I can tell the most drastic changes are in directions that involve only noise.</p> <p>Here is some matlab code:</p> <pre><code>clear all;close all;clc; %create garbage SNP-style data m = 500; n = 25000; M = zeros(m,n); %create 2 populations %one has 0s in the interesting columns %the other has 2s interesting_variables = randsample(1:n, .1*n); M(1:2:m, interesting_variables) = 2.0; %add sampling noise sigma = 4.0; M = M + double(sigma*randn(m,n) &gt; ones(m,n)); %center data for j=1:n M(:,j) = M(:,j) - mean(M(:,j)); end % plot PCA based clusters, Tygert's code is faster. tic [~,~,V] = svds(M,2); toc coordsx = zeros(1,m); coordsy = zeros(1,m); for i=1:m coordsx(i) = M(i,:)*V(:,1); coordsy(i) = M(i,:)*V(:,2); end figure() title('strcuture') plot(coordsx, coordsy, 'rx') %% % Now pick some guys from the dataset to monitor % identify them as blue triangles in the plot % some = m/5; guys = randsample(1:m, some); hold on; coordsx_blue = zeros(1,some); coordsy_blue = zeros(1,some); for i=1:some coordsx_blue(i) = M(guys(i),:)*V(:,1); coordsy_blue(i) = M(guys(i),:)*V(:,2); end plot(coordsx_blue, coordsy_blue, 'b&lt;'); %% % Finally, run PCA again but without the blue guys. % Observe how this changes the clustering when we plot the blue % against the PCs found from the reduced data % green is the new blue. % M_small = M; M_small(guys, :) = []; [ms ns] = size(M_small); tic [~,~,V_small] = svds(M_small,2); toc coordsx_newblue = zeros(1,some); coordsy_newblue = zeros(1,some); for i=1:some coordsx_newblue(i) = M(guys(i),:)*V_small(:,1); coordsy_newblue(i) = M(guys(i),:)*V_small(:,2); end plot(coordsx_newblue, coordsy_newblue, 'gh'); % draw some lines to see how things moved for i=1:some line([coordsx_blue(i) coordsx_newblue(i)], [coordsy_blue(i) coordsy_newblue(i)],'Color','c'); end </code></pre> http://mathoverflow.net/questions/16736/fast-fourier-transform-for-graph-laplacian/35392#35392 Answer by rcompton for Fast Fourier Transform for Graph Laplacian? rcompton 2010-08-12T20:12:23Z 2010-08-12T20:12:23Z <p>The trick to making the FFT work is factoring out a complex exponential from the sum over odd terms. For this to happen your function needs to be sampled across a uniform grid. Greengard refers to this property as "brittle" (cf <a href="http://math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf" rel="nofollow">math.nyu.edu/faculty/greengar/shortcourse_fmm.pdf</a> ).</p> <p>When your function is sampled over a nonuniform grid fast multipole methods or Barnes-Hut style algorithms can help.</p> http://mathoverflow.net/questions/12684/switching-research-fields/34470#34470 Answer by rcompton for Switching Research Fields rcompton 2010-08-04T03:13:00Z 2010-08-04T03:13:00Z <p>I like your style. Right now I'm distracting myself from solving a PDE arising in quantum mechanics using techniques from compressed sensing.</p> <p>Of the 3, compressed sensing is the easiest to pick up as it's more of a new signal processing trick than a fully developed research area. Checking out Candes' ICM talk (http://dsp.rice.edu/cs) as well as Igor's obsessive blog (http://nuit-blanche.blogspot.com/) does not require that much of a time commitment and can be a lot of fun. Finding research problems is another story.</p> http://mathoverflow.net/questions/27522/minimize-the-sum-of-absolute-eigenvalues/31802#31802 Answer by rcompton for minimize the sum of absolute eigenvalues rcompton 2010-07-14T06:25:39Z 2010-07-14T06:25:39Z <p>Interesting question. Nuclear norm minimization is getting much attention right now as it relates directly to compressed sensing.</p> <p>Some software for minimization with this constraint that I've used: <a href="http://perception.csl.illinois.edu/matrix-rank/sample_code.html" rel="nofollow">http://perception.csl.illinois.edu/matrix-rank/sample_code.html</a></p> <p>A fun related problem: <a href="http://www-stat.stanford.edu/~candes/papers/MatrixCompletion.pdf" rel="nofollow">http://www-stat.stanford.edu/~candes/papers/MatrixCompletion.pdf</a></p> http://mathoverflow.net/questions/121364/fixed-point-theorem-on-graphs/121367#121367 Comment by rcompton rcompton 2013-03-06T04:32:12Z 2013-03-06T04:32:12Z Wait a minute, that paper is about infinite graphs. It makes sense that I can apply it (I have a very large graph) but it's not quite the answer. http://mathoverflow.net/questions/121364/fixed-point-theorem-on-graphs/121367#121367 Comment by rcompton rcompton 2013-02-12T06:03:23Z 2013-02-12T06:03:23Z I think this will do it. I'll take a closer look at the paper over the next few days, but at a first glance it seems to treat my question exactly. http://mathoverflow.net/questions/121364/fixed-point-theorem-on-graphs/121367#121367 Comment by rcompton rcompton 2013-02-10T02:35:17Z 2013-02-10T02:35:17Z This is an interesting reference. Are there any English articles related to it? http://mathoverflow.net/questions/121364/fixed-point-theorem-on-graphs Comment by rcompton rcompton 2013-02-10T02:32:58Z 2013-02-10T02:32:58Z Oh, right, whoops, this happened on stackexchange to. My graph is very large and has a degree distribution which is (probably) power law. Edited question. http://mathoverflow.net/questions/105276/quantifying-the-amount-of-structure-in-a-data-set-via-random-matrix-theory Comment by rcompton rcompton 2012-08-23T22:20:51Z 2012-08-23T22:20:51Z Thanks. I will look into that now. http://mathoverflow.net/questions/98698/convolutive-noise-removal/98896#98896 Comment by rcompton rcompton 2012-06-05T23:12:19Z 2012-06-05T23:12:19Z Also, shouldn't that be argmax? http://mathoverflow.net/questions/98698/convolutive-noise-removal/98896#98896 Comment by rcompton rcompton 2012-06-05T23:09:33Z 2012-06-05T23:09:33Z This is what I think I'll have to do (but I'm not good with Bayesian approaches). It looks similar to Aubert and Aujol's denoising method: www.math.u-bordeaux1.fr/~jaujol/PAPERS/uv.pdf . The sticking point is that I need to minimize something non-convex in $x$. Also, I think we may need to split the $P$ across discretization points and take logs. Otherwise, well need the distribution of $\eta$ over all time which I don't think I can get. http://mathoverflow.net/questions/98698/convolutive-noise-removal/98700#98700 Comment by rcompton rcompton 2012-06-04T06:08:28Z 2012-06-04T06:08:28Z Other researchers have established, using a physical model, that this isn't white noise. A method to solve my problem is still interesting even if we have to ignore that. I'm not sure what I can learn about the correlations in time, the way we can get the density right now is to record only the noise and then use that data to generate noise statistics. We do this at t=0. There might be a way to obtain statistics at future times but I haven't figured out how to do it http://mathoverflow.net/questions/98698/convolutive-noise-removal Comment by rcompton rcompton 2012-06-04T01:38:27Z 2012-06-04T01:38:27Z We can not approximate it with a well-known distribution. It needs to be recorded each time we run an experiment. http://mathoverflow.net/questions/98698/convolutive-noise-removal/98700#98700 Comment by rcompton rcompton 2012-06-04T01:37:17Z 2012-06-04T01:37:17Z At each point in time we draw $\eta(t_i)$ from a known distribution. http://mathoverflow.net/questions/98698/convolutive-noise-removal/98700#98700 Comment by rcompton rcompton 2012-06-03T05:32:13Z 2012-06-03T05:32:13Z Yes, the $l$ and the $\eta$ hurt the sparsity. The $l$ is no problem since I have an explicit form for it. As for $\eta$, it's noise, all I know is the distribution of $\eta$. I suppose the problem I'm trying to solve is: remove additive noise + remove convolutive noise + remove convolution with $l$. http://mathoverflow.net/questions/92730/iteration-convergence Comment by rcompton rcompton 2012-03-31T01:44:00Z 2012-03-31T01:44:00Z I would just solve $(I-A)x=b$. What is this iteration you're talking about? http://mathoverflow.net/questions/87303/best-algorithm-software-for-solving-a-planar-transportation-problem/92632#92632 Comment by rcompton rcompton 2012-03-30T22:36:33Z 2012-03-30T22:36:33Z Sure. The book by Villani (who got a fields medal last time around) &quot;Topics in Optimal Transportation&quot; has more information in this field than I can give you. http://mathoverflow.net/questions/88171/efficiently-computing-a-few-localized-eigenvectors Comment by rcompton rcompton 2012-02-20T07:05:50Z 2012-02-20T07:05:50Z The setup could be described as domain decomposition for the $\triangle$ operator where $\Omega$ corresponds to one of the domains. http://mathoverflow.net/questions/88171/efficiently-computing-a-few-localized-eigenvectors Comment by rcompton rcompton 2012-02-18T23:24:21Z 2012-02-18T23:24:21Z @Squark: the integral is a sum over the indices in $\Omega$. I didn't mention it, but it's mp since $H = \triangle + V(x)$.