Elimizde $A$ matrisi var ve Frobenius Normunu hesaplamak istiyoruz. Bildiğiniz gibi Frobenius normu tüm elemanların kare toplamının kareköküne eşittir.

$$|A|_F^2 = \sum_{i,j}{A_{i,j}^2}$$

$A$'nın boyutuna $m\times n$ dersek bu işlemi yapmanın masrafı $\mathcal{O}(mn)$ olacaktır çünkü tüm elemanları hesaba katmalıyız.

Elimizde $A$'nın NMF (negatif olmayan matris ayrışımı) ile hesaplanmış çarpanlarının olduğunu düşünelim. Yani

$$A \approx W\times H$$

$W$'nun boyutu $m\times k$, $H$'nin ise $k\times n$ olsun. Ayrıca $k \ll m$ ve $k\ll n$ olsun.

Frobenius normu matrisin izinden de (trace) bulabiliriz. Yani,

$$|A|_F^2 = iz(A*A^T) = iz(W\times H \times H^T \times W^T)$$

Şimdi benim çok sevdiğim iz hilesini kullanalım. En sağdaki çarpanı sola alırsak izin değeri değişmez:

$$|A|_F^2 = iz(W^T \times W \times H \times H^T)$$

Voila! $W^T \times W$ hesabı $\mathcal{0}(m\times k^2)$'lik, $H^T \times H$ hesabı ise $\mathcal{0}(n\times k^2)$'lik bir işlem. Yani hesap etmek için toplamda $\mathcal{0}((m+n) \times k^2)$ karmaşıklığında bir işlem gerekiyor.

$k$'nın küçük olduğunu bilirsek bu gerçekten de ciddi bir hız farkı yaratıyor. Elbette elimizde çarpanların da olduğunu biliyoruz.