User zimbra314 - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T07:44:55Z http://mathoverflow.net/feeds/user/22429 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130670/error-bound-on-matrix-vector-multiplication Error bound on matrix vector multiplication zimbra314 2013-05-15T06:15:57Z 2013-05-15T22:09:02Z <p>I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate. </p> <p>Some (a very small fraction) of the element's value is changed from $a_{i,j}$ to {0,$-a_{i,j}$, $2a_{i,j}$}. However, which values are changed is not known. In fact the distribution of changed elements are uniform over elements of the matrix.We do have bound over number of elements changes $\beta\ll n^{2}$.</p> <p>Let's call the perturbation in the matrix $\Delta A$. So the matrix vector product calculated is $(A+\Delta A)p$. What I am intersted is finding bounds for following quantity</p> <p>$\eta =\frac{||\Delta Ap||}{||Ap||}$ </p> <p>I would like this bound based on all known quantities like norms of $A$ and $p$ and conditions numbers, $\beta$ etc. It can be assumed that most of the parameters about $A$ and $p$ are known.</p> <p>Edit - So far I've done is</p> <p>$\frac{\left\Vert \Delta Ap\right\Vert _{2}}{\left\Vert Ap\right\Vert }\leq\frac{\left\Vert \Delta A\right\Vert _{2}\,\left\Vert p\right\Vert _{2}}{\lambda _{n}\left\Vert p\right\Vert _{2}}\leq\frac{\left\Vert \Delta A\right\Vert _{F}}{\lambda _{n}}$</p> <p>, Here I have used 2-norm is always less then frobinius norm and $||Ap||\geq\lambda_{n}||p||$ . Here A is SPD matrix and $\lambda_{n}$ is smallest eigenvalue. Now </p> <p>$||\Delta A||_{F}^{2}=\sum _{(i,j)\in E}a _{i,j}^{2}\leq\beta(\max _{i,j}(a _{i,j}))^{2}$</p> <p>Hence</p> <p>$||\Delta A|| _{F}\leq(\max _{i,j}(a _{i,j})\sqrt{\beta})\leq\lambda _{1} \sqrt{\beta}$</p> <p>. Here again E is the set of entries in the matrix where element has been changed. and $\lambda_{1}$ is largest eigenvalue of the matrix. and $\max_{i,j}(a_{i,j})\leq\lambda_{1}$ . Hence over all I get is</p> <p>$\frac{||\Delta Ap||_{2}}{||Ap|| _{2}}\leq\kappa(A)\sqrt{\beta}$</p> <p>However, this is very loose bound since both the terms on right hand side are greater than one</p> http://mathoverflow.net/questions/129915/conjugate-gradient-algorithm-where-first-search-direction-is-not-equal-to-residua Conjugate gradient algorithm where first search direction is not equal to residual zimbra314 2013-05-07T01:15:16Z 2013-05-07T09:49:43Z <p>In usual formulation of conjugate gradient algorithm initial search direction is taken to be the residual (so residual and search direction spans Krylov subspace). However, in cases where inexact Krylov is used, search direction is not anymore in span of Krylov subspace. I am in process of analyzing convergence of one such version of CG where search directions are not anymore in span of Krylov subspace of initial residual. I wonder if any such method has been already discussed in literature. In particular, what will be condition of any instance of search direction (more than just being a descent direction) for CG to successfully converge. How does the convergence rate depends on initial search direction?</p> http://mathoverflow.net/questions/129277/problems-where-conjugate-gradient-works-much-better-than-gmres Problems where Conjugate gradient works much better than GMRES zimbra314 2013-05-01T03:17:11Z 2013-05-01T19:21:32Z <p>I am interested in cases where Conjugate gradient works much better than GMRES method.</p> <p>In general, CG is preferable choice in many cases of SPD because it requires less storage and theoretical bound on convergence rate for CG is double of that GMRES. Are there any problems where such rates are actually observed? Is there any characterization of cases where GMRES performs better or comparable to CG for same number of spmvs.</p> <p>Since Residual history is only available, in many cases to judge how well an algorithm has performed, would GMRES have always lower residual norm than CG in that case?</p> http://mathoverflow.net/questions/115421/why-do-we-need-to-specify-to-symmetric-matrix-when-defining-real-positive-definit/115429#115429 Answer by zimbra314 for why do we need to specify to symmetric matrix when defining real positive definite matrix? zimbra314 2012-12-04T17:47:05Z 2012-12-04T17:47:05Z <p>In real domain, $M$ is positive definite means $z^{T}Mz>0$ for non zero $z$. It does not means $M$ is symmetric. More generally this means symmetric part of the matrix $(M^{T}+M)/2$ is positive definite. </p> <p>While in case of complex $z^{H}Mz$ is real for all $z$ implies matrix is hermitian. Combined with $z^{H}Mz>0$, it is positive definite. ( when you say $z^{H}Mz>0$ for all $z$ it is automatically means that $z^{H}Mz$ is real for all $z$ as well.</p> http://mathoverflow.net/questions/114675/checking-for-error-in-conjugate-gradient-algorithm Checking for error in conjugate gradient algorithm zimbra314 2012-11-27T17:16:17Z 2012-11-28T14:49:06Z <p>What is a good way to check if the any numerical error is occured in conjugate gradient algorithm. Additionally why is it not suggested to check error by checking A-orthogonality of search direction or checking orthogonality of residuals?</p> <p>Note: here by error I mean error from floating point unit of CPU. In some cases the errors can be due incorrect computation of matrix vector product (in cases where matrix A is not explicitly available). </p> http://mathoverflow.net/questions/110083/understanding-discrete-cosine-transformation/110125#110125 Answer by zimbra314 for Understanding Discrete Cosine Transformation zimbra314 2012-10-20T00:50:48Z 2012-10-20T00:50:48Z <p>You're very close. $u$ corresponds to frequency and $|F(u)|$ is frequency content in the signal. Let me explain relation between variable $u$ and the frquency it corresponds to:-</p> <p>A signal is being sampled at time period of $T_{p}$, then maximum frequency that it can successfully represent is $1/2T_{p}$. Here $f=1/T_{p}$ is sampling rate and that in case of audio signal is 44.1 KHz (so that it can represent 22KHz signal which is close to hearing limit of human ears). </p> <p>Now, what all frequency it can represent depends on $N$ i.e. number of samples that you take. </p> <p>Frequency in this case will take discrete values from $0,f/N,2f/N...(N-1)f/N$ and these frequency will correspond to $u=0,1,2,..N-1$. Frequency beyond that will alias back to one those frequencies. And so more number of samples you take you can represent more number of frequency.</p> http://mathoverflow.net/questions/102389/ease-of-calculation-of-norm Ease of calculation of norm zimbra314 2012-07-16T21:22:11Z 2012-07-16T23:45:09Z <p>I have SPD matrix A and two vectors z and b.</p> <p>Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?</p> http://mathoverflow.net/questions/99473/calculating-mobius-function calculating Möbius function zimbra314 2012-06-13T16:43:11Z 2012-06-14T16:58:29Z <p>I wonder if there is any efficient way to calculate Möbius function for a array of number 1:1000000 </p> <p><a href="http://en.wikipedia.org/wiki/M%C3%B6bius_function" rel="nofollow">http://en.wikipedia.org/wiki/M%C3%B6bius_function</a></p> http://mathoverflow.net/questions/94138/matrix-elimination Matrix elimination zimbra314 2012-04-15T19:01:44Z 2012-04-16T06:11:25Z <p>$A$ is symmetric positive definite matrix and $S$ is such that $A=SS^{T}$. Further </p> <p>$y=Sz$<br> Does there exist a simple ( or any verifiable) relation exist only involving $A$,$y$ and $z$ ?</p> <p>Thanks </p> http://mathoverflow.net/questions/92328/low-rank-matrix-factorization Low rank Matrix factorization zimbra314 2012-03-26T23:45:32Z 2012-04-10T05:22:00Z <p>Hello,</p> <p>I've a SPD matrix A; which needs to be factorized as ${A=SS^{T}}$. But, using Cholesky for this purpose is prohibitive in terms of computational cost. Moreover, matrix is Dense and has a slow decaying eigen-spectrum. </p> <p>Can anything be suggested for replacement of cholesky. Moreover, it need not be exact,anything approximate will work as long as $y=Sz$ and the quantity $y^{T}y$ is what I'm trying to preserve.($z$ is standard normal vector) </p> <p>Thanks </p> http://mathoverflow.net/questions/130670/error-bound-on-matrix-vector-multiplication Comment by zimbra314 zimbra314 2013-05-16T04:59:07Z 2013-05-16T04:59:07Z we do know A has $\beta &lt;&lt; nnz(A) &lt; n^{2}$ non zero elements http://mathoverflow.net/questions/114675/checking-for-error-in-conjugate-gradient-algorithm Comment by zimbra314 zimbra314 2012-11-28T21:15:04Z 2012-11-28T21:15:04Z For discussion: look at this <a href="http://scicomp.stackexchange.com/questions/4761/checking-for-error-in-conjugate-gradient-algorithm" rel="nofollow" title="checking for error in conjugate gradient algorithm">scicomp.stackexchange.com/questions/4761/&hellip;</a> http://mathoverflow.net/questions/102389/ease-of-calculation-of-norm/102405#102405 Comment by zimbra314 zimbra314 2012-07-17T01:45:00Z 2012-07-17T01:45:00Z that is the problem with 2 norm, that it entails computing $A^{1/2}z$ which yet remains the problem. That is why in computation of $A^{-1}b$ people use $A$ norm (e.g. conjugate gradient method) cause it overcomes the problem of computing $A^{-1}z$ where z remains an approximation of x http://mathoverflow.net/questions/102389/ease-of-calculation-of-norm Comment by zimbra314 zimbra314 2012-07-16T21:29:57Z 2012-07-16T21:29:57Z sorry about confusion. I indeed meant vector norm http://mathoverflow.net/questions/99473/calculating-mobius-function/99476#99476 Comment by zimbra314 zimbra314 2012-06-13T16:53:04Z 2012-06-13T16:53:04Z I want to avoid factoring it. I'm also considering Sieve of Eratosthenes http://mathoverflow.net/questions/94138/matrix-elimination Comment by zimbra314 zimbra314 2012-04-16T01:02:30Z 2012-04-16T01:02:30Z As Igor pointed , there can be a lot of $S$ possible , which also say that there can be a number of $y$ and $S$ exist for pair of $A$ and $z$. What I'm trying to do is, suppose by some contraption I generated a $y$, (without explicitly finding out $S$ ) , I want to verify that for such $y$, there indeed exist some $S$ satisfying $A=SS^{T}$ ( again I'm not interested in calculation of S,existence is sufficient ) http://mathoverflow.net/questions/92328/low-rank-matrix-factorization Comment by zimbra314 zimbra314 2012-03-28T04:55:27Z 2012-03-28T04:55:27Z Right now I'm trying using truncated SVD; (In general it need not be low rank) Sorry about the confusion