Mixing
![what is the maximum number of different expressions (not bioconditional) you can get with n variabels in a functionally complete set? [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
If $A$ is a random matrix, $B$ is a matrix very close to the all-one matrix, then is $|Acirc B|$ close to $|A|$?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
Suppose $AinmathbbR^ntimes n$ is a symmetric random matrix with i.i.d. entries
beginalign
A_ij = A_ji =
begincases
-p & textwith probability 1-p, \
1-p & textwith probability p
endcases
endalign
for some $pin (0,1)$. If we also know $BinmathbbR^ntimes n$ is a symmetric matrix that is close to the all-one matrix $J$, i.e. there exists a small $varepsilon$ such that
beginalign
1-varepsilon leq B_ij leq 1
endalign
for any $i,jin[n]$, where $varepsilonrightarrow 0$ as $nrightarrowinfty$.
Since $A_ij$ are i.i.d. and bounded with $mathbbEA_ij = 0$, it is not hard to get a high probability bound for $|A|$ (here $|cdot|$ represents spectral norm) through Bernstein's inequality
beginalign
mathbbPleft & leq 2nexpleft(-fract^2/2mathrmVar(A) + t/3right) \
& = 2nexpleft(-fract^2/2np(1-p) + t/3right).
endalign
In other words, we have $|A| leq sqrt2p(1-p)nlog n$ with high probability.
My question is whether we could give a similar high probability bound for $Acirc B$ such that the bound gives approximately the same guarantee as the one for $A$. Intuitively, the spectral norm $|Acirc B|$ should not deviate from $|A|$ too much because $Acirc B$ and $A$ are roughly the same when $n$ is large. So can we get such a high probability bound that looks tight and utilizes the information that every entry of $Acirc B$ can only deviate from its original value in $A$ by a small portion of $varepsilon$?
Moreover, for the same random matrix $A$ if instead of $B$ there is an anti-symmetric $CinmathbbR^ntimes n$ such that
beginalign
|C_ij| leq varepsilon
endalign
for any $i,jin [n]$. Then do we have a way to utilize the fact that $C$ is anti-symmetric and obtain a better bound on $|Acirc C|$ than simply flipping the minus part of $A$ to get
beginalign
(A_C)_ij = (A_C)_ji =
begincases
varepsilon p & textwith probability 1-p, \
varepsilon (1-p) & textwith probability p
endcases
endalign
and deriving a bound through $|Acirc C|leq |A_C|$?
linear-algebra inequality norm spectral-theory random-matrices
asked Aug 6 at 14:53
ChristophorusX
1439
add a comment |Â
up vote
0
down vote
favorite
Suppose $AinmathbbR^ntimes n$ is a symmetric random matrix with i.i.d. entries
beginalign
A_ij = A_ji =
begincases
-p & textwith probability 1-p, \
1-p & textwith probability p
endcases
endalign
for some $pin (0,1)$. If we also know $BinmathbbR^ntimes n$ is a symmetric matrix that is close to the all-one matrix $J$, i.e. there exists a small $varepsilon$ such that
beginalign
1-varepsilon leq B_ij leq 1
endalign
for any $i,jin[n]$, where $varepsilonrightarrow 0$ as $nrightarrowinfty$.
Since $A_ij$ are i.i.d. and bounded with $mathbbEA_ij = 0$, it is not hard to get a high probability bound for $|A|$ (here $|cdot|$ represents spectral norm) through Bernstein's inequality
beginalign
mathbbPleft & leq 2nexpleft(-fract^2/2mathrmVar(A) + t/3right) \
& = 2nexpleft(-fract^2/2np(1-p) + t/3right).
endalign
In other words, we have $|A| leq sqrt2p(1-p)nlog n$ with high probability.
My question is whether we could give a similar high probability bound for $Acirc B$ such that the bound gives approximately the same guarantee as the one for $A$. Intuitively, the spectral norm $|Acirc B|$ should not deviate from $|A|$ too much because $Acirc B$ and $A$ are roughly the same when $n$ is large. So can we get such a high probability bound that looks tight and utilizes the information that every entry of $Acirc B$ can only deviate from its original value in $A$ by a small portion of $varepsilon$?
Moreover, for the same random matrix $A$ if instead of $B$ there is an anti-symmetric $CinmathbbR^ntimes n$ such that
beginalign
|C_ij| leq varepsilon
endalign
for any $i,jin [n]$. Then do we have a way to utilize the fact that $C$ is anti-symmetric and obtain a better bound on $|Acirc C|$ than simply flipping the minus part of $A$ to get
beginalign
(A_C)_ij = (A_C)_ji =
begincases
varepsilon p & textwith probability 1-p, \
varepsilon (1-p) & textwith probability p
endcases
endalign
and deriving a bound through $|Acirc C|leq |A_C|$?
linear-algebra inequality norm spectral-theory random-matrices
asked Aug 6 at 14:53
ChristophorusX
1439
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Suppose $AinmathbbR^ntimes n$ is a symmetric random matrix with i.i.d. entries
beginalign
A_ij = A_ji =
begincases
-p & textwith probability 1-p, \
1-p & textwith probability p
endcases
endalign
for some $pin (0,1)$. If we also know $BinmathbbR^ntimes n$ is a symmetric matrix that is close to the all-one matrix $J$, i.e. there exists a small $varepsilon$ such that
beginalign
1-varepsilon leq B_ij leq 1
endalign
for any $i,jin[n]$, where $varepsilonrightarrow 0$ as $nrightarrowinfty$.
Since $A_ij$ are i.i.d. and bounded with $mathbbEA_ij = 0$, it is not hard to get a high probability bound for $|A|$ (here $|cdot|$ represents spectral norm) through Bernstein's inequality
beginalign
mathbbPleft & leq 2nexpleft(-fract^2/2mathrmVar(A) + t/3right) \
& = 2nexpleft(-fract^2/2np(1-p) + t/3right).
endalign
In other words, we have $|A| leq sqrt2p(1-p)nlog n$ with high probability.
My question is whether we could give a similar high probability bound for $Acirc B$ such that the bound gives approximately the same guarantee as the one for $A$. Intuitively, the spectral norm $|Acirc B|$ should not deviate from $|A|$ too much because $Acirc B$ and $A$ are roughly the same when $n$ is large. So can we get such a high probability bound that looks tight and utilizes the information that every entry of $Acirc B$ can only deviate from its original value in $A$ by a small portion of $varepsilon$?
Moreover, for the same random matrix $A$ if instead of $B$ there is an anti-symmetric $CinmathbbR^ntimes n$ such that
beginalign
|C_ij| leq varepsilon
endalign
for any $i,jin [n]$. Then do we have a way to utilize the fact that $C$ is anti-symmetric and obtain a better bound on $|Acirc C|$ than simply flipping the minus part of $A$ to get
beginalign
(A_C)_ij = (A_C)_ji =
begincases
varepsilon p & textwith probability 1-p, \
varepsilon (1-p) & textwith probability p
endcases
endalign
and deriving a bound through $|Acirc C|leq |A_C|$?
linear-algebra inequality norm spectral-theory random-matrices
asked Aug 6 at 14:53
ChristophorusX
1439
Suppose $AinmathbbR^ntimes n$ is a symmetric random matrix with i.i.d. entries
beginalign
A_ij = A_ji =
begincases
-p & textwith probability 1-p, \
1-p & textwith probability p
endcases
endalign
for some $pin (0,1)$. If we also know $BinmathbbR^ntimes n$ is a symmetric matrix that is close to the all-one matrix $J$, i.e. there exists a small $varepsilon$ such that
beginalign
1-varepsilon leq B_ij leq 1
endalign
for any $i,jin[n]$, where $varepsilonrightarrow 0$ as $nrightarrowinfty$.
Since $A_ij$ are i.i.d. and bounded with $mathbbEA_ij = 0$, it is not hard to get a high probability bound for $|A|$ (here $|cdot|$ represents spectral norm) through Bernstein's inequality
beginalign
mathbbPleft & leq 2nexpleft(-fract^2/2mathrmVar(A) + t/3right) \
& = 2nexpleft(-fract^2/2np(1-p) + t/3right).
endalign
In other words, we have $|A| leq sqrt2p(1-p)nlog n$ with high probability.
My question is whether we could give a similar high probability bound for $Acirc B$ such that the bound gives approximately the same guarantee as the one for $A$. Intuitively, the spectral norm $|Acirc B|$ should not deviate from $|A|$ too much because $Acirc B$ and $A$ are roughly the same when $n$ is large. So can we get such a high probability bound that looks tight and utilizes the information that every entry of $Acirc B$ can only deviate from its original value in $A$ by a small portion of $varepsilon$?
Moreover, for the same random matrix $A$ if instead of $B$ there is an anti-symmetric $CinmathbbR^ntimes n$ such that
beginalign
|C_ij| leq varepsilon
endalign
for any $i,jin [n]$. Then do we have a way to utilize the fact that $C$ is anti-symmetric and obtain a better bound on $|Acirc C|$ than simply flipping the minus part of $A$ to get
beginalign
(A_C)_ij = (A_C)_ji =
begincases
varepsilon p & textwith probability 1-p, \
varepsilon (1-p) & textwith probability p
endcases
endalign
and deriving a bound through $|Acirc C|leq |A_C|$?
linear-algebra inequality norm spectral-theory random-matrices
asked Aug 6 at 14:53
ChristophorusX
1439
asked Aug 6 at 14:53
ChristophorusX
1439
asked Aug 6 at 14:53
ChristophorusX
1439
asked Aug 6 at 14:53
ChristophorusX
1439
1439
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14
add a comment |Â
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2873945%2fif-a-is-a-random-matrix-b-is-a-matrix-very-close-to-the-all-one-matrix-the%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
What is $A circ B$?
– copper.hat
Aug 6 at 15:12
Hadamard product. Just element-wise multiplication of $A$ and $B$.
– ChristophorusX
Aug 6 at 15:14