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