Соответствует ли асимметричная матрица Бернулли RIP?

Определите воспринимающей матрицы : с вероятностью и с вероятностью . Имеют ли удовлетворяйте ограниченную изометрию собственность ? $n\times N$ $A$ $A_{ij} = 0$ $p$ $A_{ij} = 1/\sqrt{n}$ $1-p$ $A$

Для справки, симметричный случай дан в следующей статье:

Р. Г. Баранюк, М. А. Давенпорт, Р. А. Девор и М. Б. Вакин, «Простое доказательство свойства ограниченной изометрии для случайных матриц», Конструктивное приближение, 28 (3) с. 253-263, декабрь 2008 г. ( pdf )

compressive-sensing Оливия
источник

Это может быть указатель: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5512379 (к сожалению, он расплатился, и я не нашел его OA-копию). Я не знаю документ в деталях, но я могу быстро увидеть, что они не рассматривают общий случай, как вы просите; они считают р = 1/2. Кроме того, я не знаю, насколько они тщательны в отношении RIP таких матриц.

Томас Арильдсен

Это также может быть подсказка: rauhut.ins.uni-bonn.de/RauhutSlidesLinz.pdf (стр. 98). К сожалению, похоже, что то, что он называет Бернулли, случайные переменные являются случайными +/- 1, а не 0/1 (я бы назвал их Радемахером).

Томас Арильдсен

Позвольте мне повторить суть комментария, который я сделал к тому же посту (который сейчас удален) на stats.SE : Это поможет уточнить этот вопрос и указать, что именно вас интересует и что вы пытаетесь адаптировать. Комментарий @Thomas важен; мы также не знаем, какая степень (т. е. порядок) разреженности вас интересует. Даже если мы рассмотрим функции Радемахера, ответ явно не в каком-либо равномерном (в ) смысле, так как пусть равно (или достаточно близко). ) так что существует (высокая вероятность) подматрицы, являющейся всеми единицами. (продолжение)

p

$p$

p

$p$

1

$1$

кардинал

Выбрав последовательность как функцию от , это будет сделано для некоторого для матрицы любого размера. С другой стороны, для фиксированного , если мы модифицируем конструкцию так, чтобы с вероятностью и с вероятностью , то ответ, очевидно , да , для этого следует из гораздо более общей теории , связанной с нулевым средним subgaussian случайных матриц.

p_{n} \in (0, 1)

$p_n \in (0,1)$

n

$n$

p

$p$

p

$p$

A_{i j} = (1 - p) / \sqrt{n}

$A_{ij} = (1-p)/\sqrt{n}$

p

$p$

- p / \sqrt{n}

$-p/\sqrt{n}$

(1 - p)

$(1-p)$

кардинал

Благодаря @cardinal, матрица не имеет нулевого среднего значения, но теория случайных матриц Субгаусса действительно отвечает на этот вопрос. Мне было интересно, как может удовлетворить RIP, если он не сохраняет норму, но очевидно, что есть соответствующее масштабирование которое делает это

A

$A$

A

$A$

A

$A$

olivia

Как другие заявили в комментариях, ответ «Нет». Ненулевое среднее значение матрицы диктует, что ненулевой средний вектор (скажем, все) будет иметь существенно более высокий коэффициент усиления, чем случайный вектор с нулевым средним (скажем, равномерно случайный + 1, -1).

Рассмотрим квадратичную норму A, умноженную на ожидаемый постоянный вектор y n * (p * N) ^ 2. (повторение ожиданий)

Ожидается, что квадрат A нормы для вектора x, взятого равномерно из (-1, + 1), будет n * (p * N). (рассчитывается по сумме дисперсий биномиального распределения)

Нормы x и y одинаковы, но ожидание преобразованных норм различается с коэффициентом p * N - расходящимся по мере увеличения размеров.

Вот код Matlab, чтобы помочь продемонстрировать.

n=2000;
N=1000;
p=.9;
A=double(rand(n,N)<p); 
x=sign(randn(N,1)); 
y=ones(N,1);
Ex_normSqAx = n*(N*p);  % E[ squared norm of A times random signs ]
Ex_normSqAy = n*(N*p)^2; % E[ squared norm of A times constant vector ]
normSqAx = norm(A*x)^2;
normSqAy = norm(A*y)^2;

Марк Боргердинг
источник

Соответствует ли асимметричная матрица Бернулли RIP?

Ответы: