Introduction¶
This chapters provides a framework for analysis of computational complexity of sparse recovery algorithms. See [GVL12] for a detailed study of matrix computations.
The table below summarizes the flop counts for various basic operations. A detailed derivation of these flop counts is presented in Basic Operations.
| Operation | Description | Parameters | Flop Counts |
|---|---|---|---|
| \(y = \text{abs}(x)\) | Absolute values | \(x \in \RR^n\) | \(n\) |
| \(\langle x, y \rangle\) | Inner product | \(x, y \in \RR^n\) | \(2n\) |
| \([v, i] = \text{max}(\text{abs}(x))\) | Find maximum value by magnitude | \(x \in \RR^n\) | \(2n\) |
| \(y = A x\) | Matrix vector multiplication | \(A \in \RR^{m \times n}, x \in \RR^n\) | \(2mn\) |
| \(C = AB\) | Matrix multiplication | \(A \in \RR^{m \times n}, B \in \RR^{n \times p}\) | \(2mnp\) |
| \(y = A x\) | \(A\) is diagonal | \(A \in \RR^{n\times n}, x \in \RR^n\) | \(n\) |
| \(y = A x\) | \(A\) is lower triangular | \(A \in \RR^{n\times n}, x \in \RR^n\) | \(n(n+1)\) |
| \((I + u v^T)x\) | \(x, u, v \in \RR^n\) | \(4n\) | |
| \(G = A^TA\) | Gram matrix (symmetric) | \(A \in \RR^{m \times n}\) | \(mn^2\) |
| \(F = AA^T\) | Frame operator (symmetric) | \(A \in \RR^{m \times n}\) | \(nm^2\) |
| \(\| x \|_2^2\) | Squared \(\ell_2\) norm | \(x \in \RR^n\) | \(2n - 1\) |
| \(\| x \|_2\) | \(\ell_2\) norm | \(x \in \RR^n\) | \(2n\) |
| \(x(:) = c\) | Set to a constant value | \(x \in \RR^n\) | \(n\) |
| Swap rows in \(A\) | elementary row operation | \(A \in \RR^{m \times n}\) | \(3n\) |
| \(A(i, :) = \alpha A(i, :)\) | Scale a row | \(A \in \RR^{m \times n}\) | \(2n\) |
| Solve \(L x = b\) | Lower triangular system | \(L \in \RR^{n \times n}\) | \(n^2\) |
| Solve \(U x = b\) | Upper triangular system | \(U \in \RR^{n \times n}\) | \(n^2\) |
| Solve \(Ax =b\) | Gaussian elimination, \(A\) full rank | \(A\in \RR^{n \times n}\) | \(\frac{2\, n^3}{3} + \frac{n^2}{2} - \frac{7\, n}{6}\) |
| \(A = QR\) | QR factorization | \(A \in \RR^{m \times n}\) | \(2mn^2\) |
| Solve \(\| A x - b \|_2^2\) | Least squares through QR | \(A \in \RR^{m \times n}\) | \(2mn^2 + 2mn + n^2\) |
| \(A^TA x = A^T b\) | Least squares through Cholesky \(A^T A = L L^T\) | \(A \in \RR^{m \times n}\) | \(mn^2 + \frac{1}{3} n^3\) |