WikiDer > Spark (математика)

Определение

В математикаособенно в линейная алгебра, то Искра из ${displaystyle m imes n}$ матрица ${displaystyle A}$ это наименьшее число ${displaystyle k}$ такой, что существует набор ${displaystyle k}$ столбцы в ${displaystyle A}$ которые линейно зависимый. Формально,

куда ${displaystyle d}$ - ненулевой вектор и ${displaystyle | d | _ {0}}$ обозначает его количество ненулевых коэффициентов.

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

Напротив, классифицировать матрицы - наибольшее число ${displaystyle k}$ такой, что какой-то набор ${displaystyle k}$ столбцы ${displaystyle A}$ линейно независима.

Пример

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

${displaystyle A = {egin {bmatrix} 1 & 2 & 0 & 1 1 & 2 & 0 & 2 1 & 2 & 0 & 3 1 & 0 & -3 & 4end {bmatrix}}}$

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

• Нет набора из 1 столбца ${displaystyle A}$ которые линейно зависимы.
• Нет набора из 2 столбцов ${displaystyle A}$ которые линейно зависимы.
• Но есть набор из 3 столбцов ${displaystyle A}$ которые линейно зависимы.

Первые три столбца линейно зависимы, потому что ${displaystyle {egin {pmatrix} 1 1 1 1end {pmatrix}} - {frac {1} {2}} {egin {pmatrix} 2 2 2 0end {pmatrix}} + {frac {1} {3}} {egin {pmatrix} 0 0 0 -3end {pmatrix}} = {egin {pmatrix} 0 0 0 0end {pmatrix}}}$.

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

Если ${displaystyle ngeq m}$, для искры ${displaystyle m imes n}$ матрица ${displaystyle A}$:

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

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

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

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

Если столбцы матрицы ${displaystyle A}$ нормализованы к единице норма, мы можем оценить искру матрицы снизу с точки зрения согласованности словаря:^[2]

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

Связность словаря ${displaystyle mu (A)}$ определяется как максимальная корреляция между любыми двумя столбцами, т.е.

${displaystyle mu (A) = max _ {meq n} | langle a_ {m}, a_ {n} angle |}$.

Приложения

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

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

Рекомендации