Information Technology Reference
In-Depth Information
product
C
=
A
×
B
as follows:
⎡
⎤
⎡
⎤
⎡
⎤
B
1
.
B
n
C
1
.
C
n
A
⎣
⎦
⎣
⎦
⎣
⎦
.
.
.
=
A
Here
B
i
and
C
i
are the
i
th columns of the matrices
B
and
C
, respectively. Let
B
and
C
denote the columns of these columns, respectively, and let
D
denote the block diagonal
matrix on the left.
We show that at most
2
n
2
−a−γb/
4
of the matrix pairs
(
A
,
B
)
are consistent with any
assignment to any set of
a
selected inputs and values of any
b
selected outputs.
Of the
a
selected inputs, let
a
1
be drawn from
A
and
a
2
be drawn from
B
,where
a
=
a
1
+
a
2
.Thenumberof
γ
-nice matrices
A
consistent with the
a
1
selected inputs from
A
is at most
|R|
n
2
a
1
. We now bound the number of matrices
B
that are consistent with
the values of selected inputs and outputs.
Let
A
be fixed and
γ
-nice. Consider just the (at least
b/
4) selected outputs that fall into
light columns of
C
. Every value for
B
consistent with the selected inputs and these outputs
must satisfy the following linear equation:
E
F
−
|R|
B
=
H
B
=
r
c
Here
E
consists of the
b
rows of
D
corresponding to selected outputs and
F
is a submatrix
of the
n
2
n
2
identity matrix consisting of the
a
2
rows corresponding to selected inputs
in
B
.
c
is the column of values for the selected inputs in
B
and
r
is a column of selected
outputs of
C
that fall into light columns. The number of values for
B
consistent with a
fixed
A
and the values of the selected inputs and outputs is no more than the number of
solutions
B
to these equations, since we are ignoring outputs in heavy rows.
We now show that
H
has rank at least
a
2
+
γb/
4. A column of
H
is
queried
if a column
of
E
contains a selected input or the corresponding row of
B
contains a selected input.
a
2
of these columns correspond to selected inputs in
B
and are linearly independent because
the corresponding columns of
F
are linearly independent. Consider the unqueried columns
of
H
. These columns in
F
are zero columns. Thus, consider these unqueried columns in
E
.Consider
k
rows in
E
that come from a common copy of
A
on the diagonal of
D
.The
column
B
i
of
B
corresponding to this copy of
A
is light (it has fewer than
γn
selected
entries) because the corresponding column of
C
is chosen to be light. Thus, this copy of
A
has at least
n
(
1
×
γ
)
of its columns are unqueried.
Since
A
is
γ
-nice, the unqueried columns of this copy of it have rank at least
min (
k
,
γn
)
.
Because there are no dependencies between columns in distinct copies of
A
in
D
,thenum-
ber of linearly independent unqueried columns of
E
is minimal if they all fall in as few
common copies of
A
as possible, because then
min (
k
,
γn
)=
γn
. It follows that the un-
queried columns of
E
have rank at least
γb/
4. Since the queried columns have rank at least
a
2
, the columns of
H
have rank at least
a
2
+
γb/
4. It follows from an argument given
in the proof of Lemma
10.13.2
that the number of solutions
B
to this system is at most
|R|
−
γ
)
unqueried entries, or at least
n
(
1
−
n
2
n
2
a
1
matrices
A
that are
γ
-nice and consistent
with the
a
1
selected inputs in
A
, it follows that the number of pairs consistent with values
of the selected inputs and outputs is at most
−
a
2
−
γb/
4
. Since there are at most
−
|R|
2
n
2
−a−γb/
4
, the desired conclusion.
|R|
Search WWH ::
Custom Search