Timeline for Compressing a system of linear equations
Current License: CC BY-SA 3.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2014 at 4:51 | comment | added | Yuichiro Fujiwara | @Mohsen Ah, I think I now understand where I misread your question. $A$ is a priori known to satisfy $\Gamma$? I was thinking it was unknown a priori! Sorry if I wasted your time... Anyway, Good luck! | |
| Jun 20, 2014 at 4:40 | comment | added | Helium | Thanks Yuichiro. Actually, construction of $A$ is quite complicated and too long to be described here (I am still writing it down and it's already 3 pages). But I think it's not relevant as long as $A$ has the property $\Gamma$. Anyways, thanks for your time and effort. I learned a lot from our discussion. I'll write the answer here if I found it. | |
| Jun 20, 2014 at 4:30 | comment | added | Yuichiro Fujiwara | @Mohsen Well, if $A$ is not even remotely random, my informal argument doesn't work. Sorry, but I can't know assumptions on $A$ because you didn't tell me. The question you wrote makes it sound like $A$ is taken randomly... Besides, you didn't tell whatever constrains on A you have in mind when I said you might want to impose restrictions on something. So, I guess I have to give up now because I don't know exactly what problem you want to solve... | |
| Jun 20, 2014 at 4:24 | comment | added | Helium | I think $A'=TA$ for a random matrix $T$ is not a uniformly distributed random matrix over GF$(p^q)^{k\times n}$ since it's rows are linear combinations of rows of $A$. That's why I think the result of the paper doesn't apply to my problem. | |
| Jun 20, 2014 at 4:23 | comment | added | Helium | $M$ is a feature of the system that I am designing and I have no control over it, but it can be anything. I also have some constraints for $A$. That's why $A$ is not as compact as possible. Anyways, for a given $M$, I construct $A$ in such a way that it has the desired property $\Gamma$; thus $d\ge\frac{t-1}{2}$ for $A$. But later, I want to compress it to $A'$. $A$ is not a random matrix. | |
| Jun 20, 2014 at 4:17 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
Corrected errors, improved answer, added links to original articles
|
| Jun 20, 2014 at 3:48 | comment | added | Yuichiro Fujiwara | So you should know if $d\geq\frac{t-1}{2}$. Now you didn't specify how $M$ is chosen. But, for example, assume that you may end up with $M$ with all subsets of size $c\cdot n$ for some constant $c$. In other words, your algorithm should determine if $d\geq c'\cdot n$ for some constant $c'$. Because the minimum distance of a random linear code satisfies the Gilbert-Varshamov bound with high probability, basically your algorithm should determine if $d\geq c''\cdot d$ for some constant $c''$, which seems unlikely to be in polynomial time. | |
| Jun 20, 2014 at 3:47 | comment | added | Yuichiro Fujiwara | @Mohsen A parity-check matrix $H$ doesn't have to be systematic. Take $M_x\in M$. Let $\boldsymbol{e}=(e_0,\dots,e_{n-1})$ be the $n$-dimensional vector such that $e_i=1$ if $i\in M_x$ and otherwise zero. A linear code defined by $H$ can correct error $\boldsymbol{e}$ if and only if (1) $H'$ that corresponds to columns specified by $M_x$ is full rank and (2) $H'$ with any other set of $\vert M_x\vert$ columns (which are not in $H'$) is also full rank. So, if $M$ contains all subsets of size $t$, the linear code should be of minimum distance at least $\frac{t-1}{2}$. | |
| Jun 20, 2014 at 0:45 | comment | added | Helium | I think the paper you referenced is an interesting one, but I cannot see the relation between inapproximability of $d$ and my question. Assume $M$ contains all the subsets of size $t$. Then, if I am not mistaken, my question is: Given a $[n+m, n, k]$ ECC, find a $[n+k, n, k]$ which is MDS, right? And they are both systematic ECCs. | |
| Jun 19, 2014 at 20:00 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
deleted 213 characters in body
|
| Jun 19, 2014 at 19:43 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
added 116 characters in body
|
| Jun 19, 2014 at 19:30 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
deleted 1 character in body
|
| Jun 19, 2014 at 19:25 | comment | added | Yuichiro Fujiwara | @Mohsen The randomized approach doesn't work that well. It's not in random polynomial time. See the edit of the answer. | |
| Jun 19, 2014 at 19:15 | comment | added | Yuichiro Fujiwara | @Mohsen Anyway, I revised this long comment to make it an answer. I hope this answers your question. | |
| Jun 19, 2014 at 19:11 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
deleted 63 characters in body
|
| Jun 19, 2014 at 18:50 | comment | added | Yuichiro Fujiwara | @Mohsen About $A'$ might be $TA$: But that doesn't change the situation, does it? Your definition of $\Gamma$ seems to say that $A'$ should be rows of $A$. | |
| Jun 19, 2014 at 18:47 | comment | added | Helium | I think if $M$ contains only a few $M_i$, a random matrix $T$ solves the problem with high probability, but as $|M|$ grows, a random assignment to $T$ becomes less probable to solve the problem. | |
| Jun 19, 2014 at 18:45 | comment | added | Helium | I like to add: $A'$ does not simply consist of $k$ rows of $A$. Each row of $A'$ can be a linear combination of all of rows of $A$. Since $A$ is $m\times n$ and $A'$ is $k\times n$, the question can be seen as finding a conversion matrix $T_{k\times m}$ such $A'=TA$. | |
| Jun 19, 2014 at 18:41 | comment | added | Helium | Yes, that's exactly what I mean. Thanks :) | |
| Jun 19, 2014 at 18:37 | comment | added | Yuichiro Fujiwara | @Mohsen Oh, I forgot to put "do not" before "correspond." This is what you meant, I think? | |
| Jun 19, 2014 at 18:36 | history | edited | Yuichiro Fujiwara | CC BY-SA 3.0 |
added 7 characters in body
|
| Jun 19, 2014 at 18:34 | comment | added | Helium | I correct #2: $M_i$ specifies the unknown variables, not the known ones. | |
| Jun 19, 2014 at 18:25 | history | answered | Yuichiro Fujiwara | CC BY-SA 3.0 |