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

<ul>
<li><p>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. </p></li>
<li><p>column sampling methods.</p></li>
</ul>

<p>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. <a href="http://arxiv.org/abs/1104.5557" rel="nofollow">This survey by Mahoney</a> is a useful reference for sampling methods. </p>

CC BY-SA 3.0
2013-01-03T07:08:35.397Z
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
CC BY-SA 3.0
2013-01-03T05:33:38.647Z
2013-01-03T05:33:38.647Z
Suresh Venkat
<p>If you have an efficient way of multiplying two matrices (sparse or dense), then frobenius norm should be equal to:</p>

<p>$\| A \|_F = sum(diagonal(A^T \times A))$ </p>

CC BY-SA 3.0
2013-02-20T16:18:17.380Z
2013-02-20T16:18:17.380Z
kakashi_
<p>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?</p>

CC BY-SA 3.0
2013-01-03T05:32:12.730Z
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
CC BY-SA 3.0
2013-01-03T05:34:39.100Z
Indeed, but the problem is that n is pretty large, say, 1 million. The simple loop is infeasible.
Nikita Zhiltsov
CC BY-SA 3.0
2013-01-03T05:37:55.153Z
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
CC BY-SA 3.0
2013-01-03T06:41:14.037Z
One problem with this approach is the high variance. That's what some of the more advanced sampling methods seek to address.
Suresh Venkat
<matrices>
Fast computation of Frobenius norm under memory limits
Nikita Zhiltsov
# Fast computation of Frobenius norm under memory limits

(Asked by: username_0 on 2013-01-03)

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?

**Tags:** matrices

> **Comments:**
> **username_1**: 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.  
> **username_0**: Indeed, but the problem is that n is pretty large, say, 1 million. The simple loop is infeasible.  
> **username_1**: 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.  
> **username_2**: One problem with this approach is the high variance. That's what some of the more advanced sampling methods seek to address.  

---

## 2 answers

### Answer by username_2 on 2013-01-03. Score: 3

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](http://arxiv.org/abs/1104.5557) is a useful reference for sampling methods.

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2013-02-20. Score: -1

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


---

