Spark (математика) - Spark (mathematics)

Определение

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

${displaystyle mathrm {spark} (A)=min _{deq 0}|d|_{0}{ ext{ s.t. }}Ad=0}$

(Уравнение 1)

куда ${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&11&2&0&21&2&0&31&0&-3&4end{bmatrix}}}$

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

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

Первые три столбца линейно зависимы, потому что ${displaystyle {egin{pmatrix}1111end{pmatrix}}-{frac {1}{2}}{egin{pmatrix}222�end{pmatrix}}+{frac {1}{3}}{egin{pmatrix}0��-3end{pmatrix}}={egin{pmatrix}0���end{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]

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

1. Элад, Майкл (2010). Редкие и избыточные представления от теории до приложений в обработке сигналов и изображений. стр.24.
2. Элад, Майкл (2010). Редкие и избыточные представления от теории до приложений в обработке сигналов и изображений. стр.26.
3. Донохо, Дэвид Л.; Элад, Майкл (4 марта 2003 г.), "Оптимально разреженное представление в общих (неортогональных) словарях через ℓ¹ минимизация », Proc. Natl. Акад. Sci., 100 (5): 2197–2202, Bibcode:2003ПНАС..100.2197Д, Дои:10.1073 / pnas.0437847100, ЧВК  153464, PMID  16576749
4. Тилльманн, Андреас М .; Пфетч, Марк Э. (8 ноября 2013 г.). «Вычислительная сложность свойства ограниченной изометрии, свойства пустого пространства и связанных понятий в сжатых измерениях». IEEE Transactions по теории информации. 60 (2): 1248–1259. arXiv:1205.2081. Дои:10.1109 / TIT.2013.2290112.