User zimbra314 - MathOverflow

Error bound on matrix vector multiplication

2013-05-15T06:15:57Z

I am multiplying a matrix $A$ with vector $p$. However, the matrix $A$ isn't accurate.

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}$.

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

$\eta =\frac{||\Delta Ap||}{||Ap||} $

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.

Edit - So far I've done is

$\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}}$

, 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

$||\Delta A||_{F}^{2}=\sum _{(i,j)\in E}a _{i,j}^{2}\leq\beta(\max _{i,j}(a _{i,j}))^{2}$

Hence

$||\Delta A|| _{F}\leq(\max _{i,j}(a _{i,j})\sqrt{\beta})\leq\lambda _{1} \sqrt{\beta}$

. 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

$\frac{||\Delta Ap||_{2}}{||Ap|| _{2}}\leq\kappa(A)\sqrt{\beta}$

However, this is very loose bound since both the terms on right hand side are greater than one

Conjugate gradient algorithm where first search direction is not equal to residual

2013-05-07T01:15:16Z

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?

Problems where Conjugate gradient works much better than GMRES

2013-05-01T03:17:11Z

I am interested in cases where Conjugate gradient works much better than GMRES method.

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.

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?

Answer by zimbra314 for why do we need to specify to symmetric matrix when defining real positive definite matrix?

2012-12-04T17:47:05Z

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.

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.

Checking for error in conjugate gradient algorithm

2012-11-27T17:16:17Z

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?

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).

Answer by zimbra314 for Understanding Discrete Cosine Transformation

2012-10-20T00:50:48Z

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:-

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).

Now, what all frequency it can represent depends on $N$ i.e. number of samples that you take.

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.

Ease of calculation of norm

2012-07-16T21:22:11Z

I have SPD matrix A and two vectors z and b.

Is there exist a norm where I can calculate $||A^{1/2}b-z||$ without having to calculate $A^{1/2}b$ explicitly ?

calculating Möbius function

2012-06-13T16:43:11Z

I wonder if there is any efficient way to calculate Möbius function for a array of number 1:1000000

http://en.wikipedia.org/wiki/M%C3%B6bius_function

Matrix elimination

2012-04-15T19:01:44Z

$A$ is symmetric positive definite matrix and $S$ is such that $A=SS^{T}$. Further

$y=Sz$
Does there exist a simple ( or any verifiable) relation exist only involving $A$,$y$ and $z$ ?

Thanks

Low rank Matrix factorization

2012-03-26T23:45:32Z

Hello,

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.

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)

Thanks

Comment by zimbra314

2013-05-16T04:59:07Z

we do know A has $\beta << nnz(A) < n^{2}$ non zero elements

Comment by zimbra314

2012-11-28T21:15:04Z

For discussion: look at this scicomp.stackexchange.com/questions/4761/…

Comment by zimbra314

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

Comment by zimbra314

2012-07-16T21:29:57Z

sorry about confusion. I indeed meant vector norm

Comment by zimbra314

2012-06-13T16:53:04Z

I want to avoid factoring it. I'm also considering Sieve of Eratosthenes

Comment by zimbra314

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 )

Comment by zimbra314

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