Hi:

Given a linear system y = A*x, and one does not know the

details of A. One can only understand how A acts by feeding

different x's and measures y's. In this case, how does one

estimate the Frobenius norm of A?

Thanks,
by Cheng Cosine
Mar/16/2k7 NC

On 2007-03-16 08:20:40 -0300, "Cheng Cosine" <acosine@nospam.com> said:

Hi:

Given a linear system y = A*x, and one does not know the

details of A. One can only understand how A acts by feeding

different x's and measures y's. In this case, how does one

estimate the Frobenius norm of A?

Thanks,
by Cheng Cosine
Mar/16/2k7 NC

Try x of

e_1 = ( 1, 0, 0, ... )
e_2 = ( 0, 1, 0, ... )
....
e_n = ( ..., 0, 0, 1 )

in turn and you will have all the details of A.

On Fri, 16 Mar 2007 13:31:55 +0000, Gordon Sande wrote:

On 2007-03-16 08:20:40 -0300, "Cheng Cosine" <acosine@nospam.com> said:

Hi:

Given a linear system y = A*x, and one does not know the

details of A. One can only understand how A acts by feeding

different x's and measures y's. In this case, how does one

estimate the Frobenius norm of A?
...
Try x of

e_1 = ( 1, 0, 0, ... )
e_2 = ( 0, 1, 0, ... )
....
e_n = ( ..., 0, 0, 1 )

in turn and you will have all the details of A.

and indeed if n_j is the (euclidean) norm of A*e_i,
then the Frobenius norm of A is sqrt( sum n_i*n_i),
so there's no need to store all the A*e_i

On 2007-03-16 08:20:40 -0300, "Cheng Cosine" <acos...@nospam.com> said:

Given a linear system y = A*x, and one does not know the
details of A. One can only understand how A acts by feeding
different x's and measures y's. In this case, how does one
estimate the Frobenius norm of A?

I should have mentioned another condition: A is of high dimension. So it is
highly
desired to use only "a small amount" of testing input vectors to get the
estimation.

Otherwise, just as those suggested, put any mutually orthogonal N vectors
works.

On 16 maalis, 23:47, "Cheng Cosine" <acos...@nospam.com> wrote:
On 2007-03-16 08:20:40 -0300, "Cheng Cosine" <acos...@nospam.com
said:

Given a linear system y = A*x, and one does not know the
details of A. One can only understand how A acts by feeding
different x's and measures y's. In this case, how does one
estimate the Frobenius norm of A?

I should have mentioned another condition: A is of high dimension. So it
is
highly
desired to use only "a small amount" of testing input vectors to get the
estimation.

Otherwise, just as those suggested, put any mutually orthogonal N vectors
works.

The problem I see is, the Frobenius norm is by nature difficult to
estimate unless you know each and every element. Consider a matrix
with only one nonzero element. If you don't know the location of this
element, you have to try on average O(N) trial vectors to find it.
This matrix could have arbitrarily large Frobenius norm, but you would
have no other estimate than 0 for it until the point that you've found
the element.

Maybe you have an application in mind where you do know something
about the structure of the matrix?

toni.lass...@gmail.com> wrote in message

news:1174229193.766392.82230@e1g2000hsg.googlegroups.com...



On 16 maalis, 23:47, "Cheng Cosine" <acos...@nospam.com> wrote:
On 2007-03-16 08:20:40 -0300, "Cheng Cosine" <acos...@nospam.com
said:

Given a linear system y = A*x, and one does not know the
details of A. One can only understand how A acts by feeding
different x's and measures y's. In this case, how does one
estimate the Frobenius norm of A?

I should have mentioned another condition: A is of high dimension. So it
is
highly
desired to use only "a small amount" of testing input vectors to get the
estimation.

Otherwise, just as those suggested, put any mutually orthogonal N vectors
works.

The problem I see is, the Frobenius norm is by nature difficult to
estimate unless you know each and every element. Consider a matrix
with only one nonzero element. If you don't know the location of this
element, you have to try on average O(N) trial vectors to find it.
This matrix could have arbitrarily large Frobenius norm, but you would
have no other estimate than 0 for it until the point that you've found
the element.

Maybe you have an application in mind where you do know something
about the structure of the matrix?

I'm interseted in d/u/dt = div( a*grad(u) )+q, after discretization, we
should
get dv/dt = A*v+p where A is a symmetric matrix and all eigenvalues are
negative.

But different discretization can lead to different A, e.g., finite
difference, finite element,
and so on. Is that enough to estimate A's F-norm w/o O(N) trials? Or what
are other
constraints I need to impose?

On Mar 18, 7:12 pm, "Cheng Cosine" <acos...@nospam.com> wrote:
...
For any chosen discretization method you will know that A has a
certain sparsity pattern and that the elements will be of certain
magnitude. This will certainly allow you to derive a decent lower
bound. But this calculation has to be done separately for each method,
so if you want a generic toolbox routine I'm afraid you'll have to
generate the matrices element-by-element.

toni.lassila@gmail.com> wrote in message
news:1174309028.553841.194600@l77g2000hsb.googlegroups.com...
On Mar 18, 7:12 pm, "Cheng Cosine" <acos...@nospam.com> wrote:
...
For any chosen discretization method you will know that A has a
certain sparsity pattern and that the elements will be of certain
magnitude. This will certainly allow you to derive a decent lower
bound. But this calculation has to be done separately for each method,
so if you want a generic toolbox routine I'm afraid you'll have to
generate the matrices element-by-element.


Hmm, lower bound. In the case one cannot drive the system with those
standard

basis, e.g., e_1 = <1, 0, ..., 0>, but can only use a set of linearly
independent vectors,

how to estimate this lower bound for du/dt = A*u+q? Can this estimate be
determined

by a set of q's or must be determined by a set of initial u's?

Thanks,
by Cheng Cosine
Mar/19/2k7 NC


up to this point anyone who answered thought that you can apply the