Искра (математика)

В математике , а точнее в линейной алгебре , зажглась искра $m\times n$ матрица $A$ это наименьшее целое число $k$ такая, что существует набор $k$ столбцы в $A$ которые линейно зависимы . Если все столбцы линейно независимы, $\mathrm {spark} (A)$ обычно определяется на 1 больше, чем количество строк. Концепция матричной искры находит применение в кодах с исправлением ошибок , компрессионном зондировании и теории матроидов и обеспечивает простой критерий максимальной разреженности решений системы линейных уравнений .

Искру матрицы NP-трудно вычислить.

Определение

Формально искра матрицы $A$ определяется следующим образом:

$\mathrm {spark} (A)=\min _{d\neq 0}\|d\|_{0}{\text{ s.t. }}Ad=0$ ( Уравнение 1 )

где $d$ ненулевой вектор и $\|d\|_{0}$ обозначает количество ненулевых коэффициентов ( $\|d\|_{0}$ также называется размером носителя вектора). Эквивалентно искре матрицы $A$ это размер его наименьшей цепи $C$ (подмножество индексов столбцов такое, что $A_{C}x=0$ имеет ненулевое решение, но каждое его подмножество не имеет ).

Если все столбцы линейно независимы, $\mathrm {spark} (A)$ обычно определяется как $m+1$ (если $A$ имеет m строк).

Напротив, ранг матрицы — это наибольшее число $k$ такой, что некоторый набор $k$ столбцы $A$ линейно независима.

Пример

Рассмотрим следующую матрицу $A$.

$A={\begin{bmatrix}1&2&0&1\\1&2&0&2\\1&2&0&3\\1&0&-3&4\end{bmatrix}}$

Искра этой матрицы равна 3, потому что:

• Нет набора из 1 столбца $A$ которые линейно зависимы.
• Нет набора из 2 столбцов $A$ которые линейно зависимы.
• Но есть набор из 3 столбцов $A$ которые линейно зависимы. Первые три столбца линейно зависимы, поскольку ${\begin{pmatrix}1\\1\\1\\1\end{pmatrix}}-{\frac {1}{2}}{\begin{pmatrix}2\\2\\2\\0\end{pmatrix}}+{\frac {1}{3}}{\begin{pmatrix}0\\0\\0\\-3\end{pmatrix}}={\begin{pmatrix}0\\0\\0\\0\end{pmatrix}}$.

Характеристики

Если $n\geq m$, для искры $m\times n$ матрица $A$:

• $\mathrm {spark} (A)=m+1\Rightarrow \mathrm {rank} (A)=m$ (Если искра равна $m+1$, то матрица имеет полный ранг.)
• $\mathrm {spark} (A)=1$ тогда и только тогда, когда матрица имеет нулевой столбец.
• $\mathrm {spark} (A)\leq \mathrm {rank} (A)+1$.

Критерий единственности разреженных решений.

Искра дает простой критерий единственности разреженных решений систем линейных уравнений . Дана система линейных уравнений $A\mathbf {x} =\mathbf {b}$. Если эта система имеет решение $\mathbf {x}$ это удовлетворяет $\|\mathbf {x} \|_{0}<{\frac {\mathrm {spark} (A)}{2}}$, то это решение является самым разреженным из возможных решений. Здесь $\|\mathbf {x} \|_{0}$ обозначает количество ненулевых элементов вектора $\mathbf {x}$.

Нижняя граница с точки зрения связности словаря

Если столбцы матрицы $A$ нормализованы к единичной норме , мы можем оценить ее искру снизу с точки зрения согласованности словаря:

$\mathrm {spark} (A)\geq 1+{\frac {1}{\mu (A)}}$.

Здесь связность словаря $\mu (A)$ определяется как максимальная корреляция между любыми двумя столбцами:

$\mu (A)=\max _{m\neq n}|\langle a_{m},a_{n}\rangle |=\max _{m\neq n}{\frac {|a_{m}^{\intercal }a_{n}|}{||a_{m}||_{2}||a_{n}||_{2}}}$.

Приложения

Минимальное расстояние линейного кода равно искре его матрицы проверки четности .

Концепция искры также используется в теории компрессионного зондирования , где требования к искре матрицы измерений используются для обеспечения стабильности и последовательности различных методов оценки. он также известен В теории матроидов как обхват векторного матроида, связанного со столбцами матрицы. Искру матрицы NP-трудно вычислить.