toqito.matrix_props.spark

Computes the spark of a matrix.

Module Contents

toqito.matrix_props.spark.spark(mat)[source]

Compute the spark of a matrix.

The spark of a matrix A is the smallest number of columns from A that are linearly dependent [@Elad_2010_Sparse].

Examples

```python exec=”1” source=”above” import numpy as np from toqito.matrix_props import spark

A = np.array([[1, 0, 1, 2],

[0, 1, 1, 3], [1, 1, 2, 5]])

print(spark(A)) ```

Notes

  • This function only works for 2D NumPy arrays.

  • If all columns are linearly independent, the function returns n_cols + 1.

  • The time complexity of this implementation is O(2^n) in the worst case, where n is the number of columns.

  • For an m x n matrix A with n >= m:

    • If spark(A) = m + 1, then rank(A) = m (full rank).

    • If spark(A) = 1, then the matrix has a zero column.

    • If spark(A) <= rank(A) + 1, then the matrix has dependent columns.

Raises:

ValueError – If the input is not a 2D NumPy array.

Parameters:

mat (numpy.ndarray) – The input matrix as a 2D NumPy array.

Returns:

The spark of the input matrix mat.

Return type:

int