Fdtxjr

Why does this iterative way of solving of equation work?

Are my PIs rude or am I just being too sensitive?

What items from the Roman-age tech-level could be used to deter all creatures from entering a small area?

Why is "Captain Marvel" translated as male in Portugal?

Limit for e and 1/e

Geometric mean and geometric standard deviation

Two different pronunciation of "понял"

How does modal jazz use chord progressions?

Stop battery usage [Ubuntu 18]

Is above average number of years spent on PhD considered a red flag in future academia or industry positions?

I'm thinking of a number

How to market an anarchic city as a tourism spot to people living in civilized areas?

How are presidential pardons supposed to be used?

Passing functions in C++

How to say that you spent the night with someone, you were only sleeping and nothing else?

Autumning in love

Who can trigger ship-wide alerts in Star Trek?

I'm having difficulty getting my players to do stuff in a sandbox campaign

What computer would be fastest for Mathematica Home Edition?

Notation for two qubit composite product state

Writing Thesis: Copying from published papers

Estimate capacitor parameters

Can a zero nonce be safely used with AES-GCM if the key is random and never used again?

How is simplicity better than precision and clarity in prose?

How to simplify repeated convolution and Hadamard multiplication

1

$begingroup$

I’ve determined that the following expression gives me the correct answer in a programming challenge:

$$ (A circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) $$

… for a certain number of $(circledast M times H)$ iterations, where A, M, and H are matrices (M is symmetric, and H is binary (each entry is either zero or one)), $circledast$ is convolution, and $times$ is Hadamard (pointwise) multiplication.

However this approach is slightly too slow to be an acceptable solution. If I could only simplify the above expression to something like:

$$A circledast ( M circledast M circledast M ... circledast M ) $$

then I would be able to speed up calculating the M-convolutions by grouping it into calculating M2=(M*M), M4=(M2*M2), etc, finishing with $(A circledast M300)$ and the runtime would be well within acceptable bounds.

However I cannot figure out how to include the pointwise multiplication in any simplified equation resembling the second form. $(A times H) circledast (M times H)$ doesn't seem to give an equivalent expression, for example, nor does any of my attempts at splitting up A into (A1-A2) corresponding to the binary entries of H and subtracting the results back together at the end.

Is there a way to use properties of Hadamard multiplication and/or convolution to achieve this simplification?

matrices convolution hadamard-product

share|cite|improve this question

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

$endgroup$

add a comment | 

1

$begingroup$

I’ve determined that the following expression gives me the correct answer in a programming challenge:

$$ (A circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) $$

… for a certain number of $(circledast M times H)$ iterations, where A, M, and H are matrices (M is symmetric, and H is binary (each entry is either zero or one)), $circledast$ is convolution, and $times$ is Hadamard (pointwise) multiplication.

However this approach is slightly too slow to be an acceptable solution. If I could only simplify the above expression to something like:

$$A circledast ( M circledast M circledast M ... circledast M ) $$

then I would be able to speed up calculating the M-convolutions by grouping it into calculating M2=(M*M), M4=(M2*M2), etc, finishing with $(A circledast M300)$ and the runtime would be well within acceptable bounds.

However I cannot figure out how to include the pointwise multiplication in any simplified equation resembling the second form. $(A times H) circledast (M times H)$ doesn't seem to give an equivalent expression, for example, nor does any of my attempts at splitting up A into (A1-A2) corresponding to the binary entries of H and subtracting the results back together at the end.

Is there a way to use properties of Hadamard multiplication and/or convolution to achieve this simplification?

matrices convolution hadamard-product

share|cite|improve this question

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

$endgroup$

add a comment | 

$begingroup$

I’ve determined that the following expression gives me the correct answer in a programming challenge:

$$ (A circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) circledast M) times H) $$

… for a certain number of $(circledast M times H)$ iterations, where A, M, and H are matrices (M is symmetric, and H is binary (each entry is either zero or one)), $circledast$ is convolution, and $times$ is Hadamard (pointwise) multiplication.

However this approach is slightly too slow to be an acceptable solution. If I could only simplify the above expression to something like:

$$A circledast ( M circledast M circledast M ... circledast M ) $$

then I would be able to speed up calculating the M-convolutions by grouping it into calculating M2=(M*M), M4=(M2*M2), etc, finishing with $(A circledast M300)$ and the runtime would be well within acceptable bounds.

However I cannot figure out how to include the pointwise multiplication in any simplified equation resembling the second form. $(A times H) circledast (M times H)$ doesn't seem to give an equivalent expression, for example, nor does any of my attempts at splitting up A into (A1-A2) corresponding to the binary entries of H and subtracting the results back together at the end.

Is there a way to use properties of Hadamard multiplication and/or convolution to achieve this simplification?

matrices convolution hadamard-product

share|cite|improve this question

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

$endgroup$

share|cite|improve this question

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

share|cite|improve this question

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61

asked Mar 25 at 19:31

N. WhitcherN. Whitcher

61