Thread Subject: what regularization is used in slash operator on sparse rank

Hi
I use slash to solve the system A x =b
and my A is sparse rank deficient matrix.

Do you know what kind of regularization is used by matlab?
Tikhonov regularization?

Thanks

kem <kemelmi@gmail.com> wrote in message <ee27d999-1bea-4292-a8f2-
a43816048705@2g2000hsn.googlegroups.com>...
> Hi
> I use slash to solve the system A x =b
> and my A is sparse rank deficient matrix.
>
> Do you know what kind of regularization is used by matlab?
> Tikhonov regularization?
>
> Thanks

There is none used. Why would you expect
something?

John

On May 12, 3:57=A0pm, "John D'Errico" <woodch...@rochester.rr.com>
wrote:
> kem <keme...@gmail.com> wrote in message <ee27d999-1bea-4292-a8f2-
>
> a43816048...@2g2000hsn.googlegroups.com>...
>
> > Hi
> > I use slash to solve the system A x =3Db
> > and my A is sparse rank deficient matrix.
>
> > Do you know what kind of regularization is used by matlab?
> > Tikhonov regularization?
>
> > Thanks
>
> There is none used. Why would you expect
> something?
>
> John

because it is rank deficient? how does it solve this problem?

thanks

"kem" <kemelmi@gmail.com> wrote in message
news:bb922216-50e8-496d-91ae-ed7cde6e9476@s50g2000hsb.googlegroups.com...
On May 12, 3:57 pm, "John D'Errico" <woodch...@rochester.rr.com>
wrote:
> kem <keme...@gmail.com> wrote in message <ee27d999-1bea-4292-a8f2-

*snip*

> because it is rank deficient? how does it solve this problem?

Read the Algorithm section from this page in the documentation:

http://www.mathworks.com/access/helpdesk/help/techdoc/ref/mldivide.html

--
Steve Lord
slord@mathworks.com

On May 12, 4:23=A0pm, "Steven Lord" <sl...@mathworks.com> wrote:
> "kem" <keme...@gmail.com> wrote in message
>
> news:bb922216-50e8-496d-91ae-ed7cde6e9476@s50g2000hsb.googlegroups.com...
> On May 12, 3:57 pm, "John D'Errico" <woodch...@rochester.rr.com>
> wrote:
>
> > kem <keme...@gmail.com> wrote in message <ee27d999-1bea-4292-a8f2-
>
> *snip*
>
> > because it is rank deficient? how does it solve this problem?
>
> Read the Algorithm section from this page in the documentation:
>
> http://www.mathworks.com/access/helpdesk/help/techdoc/ref/mldivide.html
>
> --
> Steve Lord
> sl...@mathworks.com

My matrix is sparse, with m>n, banded and rank deficient. Does it mean
that Matlab's slash uses "CHOLMOD " ?

kem <kemelmi@gmail.com> wrote in message
...
> My matrix is sparse, with m>n, banded and rank deficient.
Does it mean
> that Matlab's slash uses "CHOLMOD " ?

No. It uses a sparse QR factorization written by John
Gilbert, based on row-wise Givens rotations. I'm not sure
what level of rank-estimation it does, but it at least uses
some form of tolerance (if a column's rank drops below tol,
then it is declared redundant). For the dense case,

tol = size(A,1) * eps * max(abs(diag(A'*A)))

which is probably used for the sparse case. By detecting
redundant columns, the MATLAB sparse QR attempts to return a
"basic" solution. See Section 5.7 in:

http://www.mathworks.com/moler/leastsquares.pdf

Can you send me your matrix? I'd like to take a look. I
don't have that many rank-deficient least squares matrices
in my collection (
http://www.cise.ufl.edu/research/sparse/matrices) . More
matrices in that domain means that future algorithms will do
a better job at solving your problem.

You can submit matrices to http://www.cise.ufl.edu/~web-gfs

Thanks,
Tim Davis (author of CHOLMOD, UMFPACK, etc)