Аппроксимация знака ранга матрицы

25

Знаковый ранг матрицы A с элементами + 1, -1 является наименьшим рангом (по реалам) матрицы B, которая имеет такой же шаблон знака, что и A (то есть для всех i , к ). Это понятие важно в сложности общения и теории обучения.AяJВяJ>0я,J

Мой вопрос: существуют ли какие-либо известные (субэкспоненциальные по времени) алгоритмы, которые аппроксимируют ранговый знак матрицы с точностью до множителя ?о(N)

(Мне известна нижняя граница Форстера для ранга знака в терминах спектральной нормы, но это не дает отношения аппроксимации лучше, чем в целом.)Ω(N)

Moritz
источник

Ответы:

17

Я считаю, что это открытый вопрос.

Ли и Шрайбман в «Алгоритме аппроксимации для ранга аппроксимации» показывают, что ранг аппроксимации может быть аппроксимирован с постоянным множителем алгоритмом полиномиального времени. Для этого они связывают полуопределенную программную величину с рангом аппроксимации, где α - некоторый конечный параметр, больший 1. Приведение α к пределу бесконечности дает ранг знака, но их результат ничего не дает в этом установка.γ2ααα

Арнаб
источник
12

О(N/журналN)dS

  • MSрaNК Mзнак равноО(N1-1/d)
  • Sd

MО(N1-1/d/d)dзнак равноΘ(журналN)

Сашо Николов
источник