Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Given a large dense matrix $A^{n \times n}$, that does not fit to the memory (RAM). Is there any fast way to compute the exact Frobenius norm of the matrix or its accurate approximation (perhaps, via sampling with reasonable bounds provided)? What if this matrix is a subtraction of two $n \times n$ matrices: $\| A - B \|_F$, where $A$ is sparse, and B is dense?

share|improve this question
    
Wikipedia defines the Frobenius norm as $\|A\|_F^2 = \sum_{i,j} A_{ij}^2$, so if you can compute all the entries of $A$, you should be able to compute its Frobenius norm. –  Yuval Filmus Jan 3 '13 at 5:32
    
Indeed, but the problem is that n is pretty large, say, 1 million. The simple loop is infeasible. –  Nikita Zhiltsov Jan 3 '13 at 5:34
3  
We also have $\|A\|_F^2 = n^2 E[\alpha^2]$, where $\alpha$ is a random entry of the matrix. So you can estimate the norm by sampling. –  Yuval Filmus Jan 3 '13 at 5:37
2  
One problem with this approach is the high variance. That's what some of the more advanced sampling methods seek to address. –  Suresh Venkat Jan 3 '13 at 6:41
add comment

2 Answers 2

Some of the results depend on the model under which the matrix is presented, but there's a large collection of results that use sampling or sketching techniques to estimate norms accurately. Among some of the key results are:

  • sketching methods based on the use of 2-stable distributions: these work even if the entries are "streamed in" in some order, and also work if you are presented instead with the A and the B entries.

  • column sampling methods.

Again, it would be unfair to single out a single paper, also because it's not exactly clear which model you're working in: best to google 'norm estimation' or 'column sampling' to find some of the related results. This survey by Mahoney is a useful reference for sampling methods.

share|improve this answer
    
Thanks, this looks helpful. –  Nikita Zhiltsov Jan 3 '13 at 5:40
    
It's interesting that, due to the sparsity of matrix A (I anticipate O(n) non-zero values in it) in (A - B), one may compute the exact part of Frobenius norm for corresponding (a-b) elements, and sample from a distribution over remaining elements and compute the approximation only using B elements. Sorry about the cluttered notation. –  Nikita Zhiltsov Jan 3 '13 at 7:08
add comment

If you have an efficient way of multiplying two matrices (sparse or dense), then frobenius norm should be equal to:

$\| A \|_F = sum(diagonal(A^T \times A))$

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.