(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 155262, 5250]*) (*NotebookOutlinePosition[ 164264, 5525]*) (* CellTagsIndexPosition[ 162309, 5458]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["Notes", "Section 1"], Cell[CellGroupData[{ Cell["Editorial Changes", "Subsection"], Cell["\<\ \"Footnotes\" section added to end of the paper to list the single footnote \ that originally appeared at the foot of one page. A hyperlink to this \ footnote has also been added to the body of the paper.\ \>", "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change1", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "Figure moved to a more appropriate point in the text." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["PROBLEM", ButtonData:>"Ed:Problem1", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ SubscriptBox[\(\([\)\(\[CenterEllipsis]\)\(]\)\), RowBox[{ StyleBox["y", FontWeight->"Bold"], "=", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]], TraditionalForm]]], "\" rather than \"", Cell[BoxData[ FormBox[ RowBox[{"\[CenterEllipsis]", SubscriptBox["|", RowBox[{ StyleBox["y", FontWeight->"Bold"], "=", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]]}], TraditionalForm]]], "\" is used because ", StyleBox["Mathematica", FontSlant->"Italic"], " can't display the latter correctly." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change2", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox["P", StyleBox["x", FontWeight->"Bold"]], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], "\", and \"", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["D", FontSlant->"Italic"]}]], StyleBox["/", FontSlant->"Italic"], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]], TextAlignment->AlignmentMarker, SpanMaxSize->Infinity], "\" changed to \"", Cell[BoxData[ FormBox[ FractionBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["D", FontSlant->"Italic"]}]], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], TraditionalForm]], TextAlignment->AlignmentMarker, SpanMaxSize->Infinity], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change3", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{"arg", GridBox[{ {"min"}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], ")"}], "2"]}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ RowBox[{GridBox[{ {\(arg\ min\)}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change4", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{"arg", GridBox[{ {"min"}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}], "2"]}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ RowBox[{GridBox[{ {\(arg\ min\)}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], "\[RightBracketingBar]"}], "2"]}], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change5", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(\(-1\)/N\)], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(-\(1\/N\)\)], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change17", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"ie\" changed to \"i.e.\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change6", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`\( \[Rule] \&\[SelectionPlaceholder]\)\)]], "\" changed to \"", Cell[BoxData[ \(TraditionalForm\`\(\[LongRightArrow]\&\[SelectionPlaceholder]\)\)]], "\" twice." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change7", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"[8]\" changed to \"[8].\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change8", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-\[Sigma]\)/\[Sigma]\_0\)\)]], "\" changed to \"", Cell[BoxData[ \(TraditionalForm\`e\^\(-\(\[Sigma]\/\[Sigma]\_0\)\)\)]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change9", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-I\)/I\_0\)\)]], "\" changed to \"", Cell[BoxData[ \(TraditionalForm\`e\^\(-\(I\/I\_0\)\)\)]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change10", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change13", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-I\)/\[Sigma] - \[Sigma]/\[Sigma]\_0\)\)]], "\" changed to \"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-\(I\/\[Sigma]\)\) - \ \[Sigma]\/\[Sigma]\_0\)\)]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change11", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-\[Beta]\)/x - \[Gamma]\ x\)\)]], "\" changed to \"", Cell[BoxData[ \(TraditionalForm\`e\^\(\(-\(\[Beta]\/x\)\) - \[Gamma]\ x\)\)]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change12", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ \(TraditionalForm\`I\)]], "-dependence\" changed to \"", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], "-dependence\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change14", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"equation (30)\" changed to \"equation (30).\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change15", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], "/", RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]}], "\[RightBracketingBar]"}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], TraditionalForm]]], "\"." }], "Text"], Cell[TextData[{ Cell[BoxData[ FormBox[ ButtonBox["TYPO", ButtonData:>"Ed:Change16", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], "\"", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Sigma]", FontSlant->"Italic"]}]], StyleBox["/", FontSlant->"Italic"], StyleBox[ RowBox[{"d", StyleBox["I", FontSlant->"Italic"]}]]}], TraditionalForm]]], "\" changed to \"", Cell[BoxData[ FormBox[ FractionBox[ StyleBox[ RowBox[{"d", StyleBox["\[Sigma]", FontSlant->"Italic"]}]], StyleBox[ RowBox[{"d", StyleBox["I", FontSlant->"Italic"]}]]], TraditionalForm]]], "\"." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ "Vector quantisation of ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data\n" }], "Title"], Cell["\<\ Stephen P Luttrell Pattern Processing Principles SP4 division, RSRE Malvern, WORCS, WR14 3PS\ \>", "Author"], Cell["\<\ This paper appeared as SP4 Research Note, No. 110, 12 February 1990.\ \>", "Text"], Cell["Copyright \[Copyright] Controller HMSO, London, 1990.", "Text"], Cell[TextData[{ StyleBox["Abstract", FontWeight->"Bold"], "\n\nI apply an extension [", ButtonBox["1", ButtonData:>"Ref:EphraimGray1988", ButtonStyle->"Hyperlink"], "] of the standard LBG vector quantisation algorithm [", ButtonBox["2", ButtonData:>"Ref:LindeBuzoGray1980", ButtonStyle->"Hyperlink"], "] to the problem of encoding ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data [", ButtonBox["3", ButtonData:>"Ref:JakemanPusey1976", ButtonStyle->"Hyperlink"], ", ", ButtonBox["4", ButtonData:>"Ref:Ward1980", ButtonStyle->"Hyperlink"], ", ", ButtonBox["5", ButtonData:>"Ref:Ward1981", ButtonStyle->"Hyperlink"], "], with the intention of eventually recovering the underlying cross \ section. I also derive some useful approximations for the distortion that \ this coding scheme introduces." }], "Abstract"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " Introduction" }], "Section 1"], Cell[TextData[{ "I shall motivate the use of quantisation techniques and their application \ to ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data." }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Quantisation techniques" }], "Subsection"], Cell["\<\ Quantisation is used to reduce datasets to a more manageable size, whilst \ retaining their essential information content. There is a variety of \ techniques, each with its own peculiar advantages. The choice of which \ particular technique is appropriate depends on exactly what type of \ information one wishes to preserve in the reduced data, and on how much \ memory and time one has at one's disposal for encoding/decoding purposes.\ \>", "Text"], Cell[TextData[{ "Scalar quantisation is the simplest technique [", ButtonBox["6", ButtonData:>"Ref:Max1960", ButtonStyle->"Hyperlink"], ", ", ButtonBox["7", ButtonData:>"Ref:Lloyd1982", ButtonStyle->"Hyperlink"], "] - it merely amplitude quantises data samples independently. This can be \ generalised by grouping together the data samples in batches, and then vector \ quantising each batch ", "[", ButtonBox["2", ButtonData:>"Ref:LindeBuzoGray1980", ButtonStyle->"Hyperlink"], "]", ". This allows the quantisation to take advantage of correlations amongst \ the data samples to reduce the data further than scalar quantisation. In \ fact, even if the data samples are independently distributed, a greater data \ reduction can be obtained by using vector quantisation." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data" }], "Subsection"], Cell[TextData[{ "It is an empirical result that many types of radar clutter follow have \ statistical properties that are well modelled as a ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distribution [", ButtonBox["3", ButtonData:>"Ref:JakemanPusey1976", ButtonStyle->"Hyperlink"], ", ", ButtonBox["4", ButtonData:>"Ref:Ward1980", ButtonStyle->"Hyperlink"], ", ", ButtonBox["5", ButtonData:>"Ref:Ward1981", ButtonStyle->"Hyperlink"], "]. Thus the data samples (or pixels) are corrupted by multiplicative noise \ which masks the ideal clean data value. Any information processing technique \ must acknowledge this fact and attempt to reject the noise content of the \ data (whilst attempting to retain its signal content, of course). For \ instance, incoherent averaging of several contiguous data samples has the \ required effect, at the cost of some loss of resolution." }], "Text"], Cell[TextData[{ "In this note I shall be concemed with vector quantisation of ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data, with the intention of reconstructing the underlying \ clean data. This is a particular instance of information processing of a \ noisy signal, and its success is dependent on the accuracy of both the noise \ model and the model of the underlying clean data (caveat!)." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Structure of this note" }], "Subsection"], Cell[TextData[{ "In ", ButtonBox["\[Section]", ButtonData:>"Sect:2", ButtonStyle->"Hyperlink"], CounterBox["Section", "Sect:2"], " I shall summarise vector quantisation theory, leading to the \ Linde-Buzo-Gray (LBG) algorithm [", ButtonBox["2", ButtonData:>"Ref:LindeBuzoGray1980", ButtonStyle->"Hyperlink"], "], and in ", ButtonBox["\[Section]", ButtonData:>"Sect:3", ButtonStyle->"Hyperlink"], CounterBox["Section", "Sect:3"], " I shall review an extension of this algorithm that can vector quantise \ noisy data [", ButtonBox["1", ButtonData:>"Ref:EphraimGray1988", ButtonStyle->"Hyperlink"], "]. In ", ButtonBox["\[Section]", ButtonData:>"Sect:4", ButtonStyle->"Hyperlink"], CounterBox["Section", "Sect:4"], " I shall derive some approximate expressions for the reconstruction \ distortion. Finally, in ", ButtonBox["\[Section]", ButtonData:>"Sect:5", ButtonStyle->"Hyperlink"], CounterBox["Section", "Sect:5"], " I shall indicate how these results could be applied to the problems of \ scalar and vector quantisation of ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data." }], "Text"], Cell["\<\ I shall develop all the theory in a continuous (rather than discrete) \ notation because this lends itself well to producing simple and direct \ derivations of continuum versions of numerical algorithms. Actual algorithms \ are, of course, discrete in nature. However, conversion between the continuum \ and discrete versions of algorithms is simple - integrations are exchanged \ for summations, etc.\ \>", "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Vector quantisation" }], "Section", CellTags->"Sect:2"], Cell[TextData[{ "In this section I shall present and discuss a simple derivation of the \ Linde-Buzo-Gray (LBG) vector quantisation method. See ", "[", ButtonBox["2", ButtonData:>"Ref:LindeBuzoGray1980", ButtonStyle->"Hyperlink"], "]", " for the original derivation of this method." }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Notation" }], "Subsection"], Cell["Throughout this section I shall use the following notation.", "Text"], Cell[TextData[{ "\t", Cell[BoxData[ FormBox[GridBox[{ { StyleBox["x", FontWeight->"Bold"], StyleBox[\(Input\ data\ vector\), FontSize->11]}, { SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], StyleBox[\(Reconstructed\ data\ vector\), FontSize->11]}, { StyleBox["y", FontWeight->"Bold"], StyleBox[\(Encoded\ data\), FontSize->11]}, { RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], StyleBox[\(The\ encoding\ operation\), FontSize->11]}, { RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], StyleBox[\(The\ decoding\ operation\), FontSize->11]}, { RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox[\(Probability\ density\ function\ \((PDF)\)\ of\ input\ \ vectors\), FontSize->11]}, { RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], RowBox[{ StyleBox["Distortion", FontSize->11], StyleBox[" ", FontSize->11], StyleBox["measure", FontSize->11], StyleBox[" ", FontSize->11], StyleBox["between", FontSize->11], StyleBox[" ", FontSize->11], StyleBox["x", FontSize->11, FontWeight->"Bold"], StyleBox[" ", FontSize->11], StyleBox["and", FontSize->11], StyleBox[" ", FontSize->11], StyleBox[ SuperscriptBox[ StyleBox["x", FontSize->11, FontWeight->"Bold"], "\[Prime]"], FontSize->11]}]}, {"D", StyleBox[\(Average\ distortion\), FontSize->11]} }], TraditionalForm]]] }], "Text", GridBoxOptions->{ColumnAlignments->{Left}}], Cell[TextData[{ "Both here and elsewhere in this note I shall use the notation ", Cell[BoxData[ \(TraditionalForm\`P( . )\)]], " generically to denote \"the probability density of\". This notation is \ not to be construed as meaning that all the PDFs have the same functional \ form - this is to be deduced from the context." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Encoding and decoding data" }], "Subsection"], Cell[TextData[{ "The input data vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " is encoded using ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " to produce a reduced version ", Cell[BoxData[ FormBox[ StyleBox["y", FontWeight->"Bold"], TraditionalForm]]], " of the data. In turn, ", Cell[BoxData[ FormBox[ StyleBox["y", FontWeight->"Bold"], TraditionalForm]]], " is decoded using ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " to produce a reconstructed input vector ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], TraditionalForm]]], " which is supposed to be a close approximation to the original ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ". These steps are summarised as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ StyleBox["x", FontWeight->"Bold"], OverscriptBox["\[LongRightArrow]", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], RowBox[{ StyleBox["y", FontWeight->"Bold"], StyleBox[ OverscriptBox[ StyleBox["\[LongRightArrow]", FontWeight->"Plain"], RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]], FontWeight->"Plain"], SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:1"], Cell[TextData[{ "This can be thought of as an unsupervised neural network with one hidden \ layer, in which the layer to layer mappings are ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], "." }], "Text"], Cell[TextData[Cell[TextData[{ " ", ButtonBox["OPEN", ButtonData:>{ URL[ "http://www.luttrell.org.uk/papers/sp4_110/fig1.gif"], None}, Active->True, ButtonStyle->"Hyperlink"], " " }]]], "NumberedFigure", TextAlignment->Center, CellTags->{"Fig:1", "Ed:Change1"}], Cell["Encoding and decoding clean input data", "Caption"], Cell[TextData[{ "In ", ButtonBox["Figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], " I represent the encoding and decoding process (of ", ButtonBox["equation", ButtonData:>"Eq:1", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:1"], ")) pictorially. For convenience, I have folded this diagrain so that the \ input and output spaces are adjacent." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Distortion measure" }], "Subsection"], Cell[TextData[{ "The distortion measure ", Cell[BoxData[ FormBox[ RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], TraditionalForm]]], " quantifies the error which is induced on ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " by the combined encoding/decoding operation. One's notion of what is a \ small or large error depends entirely on what one wishes to use the data for. \ The derivation that I shall present is not dependent on a particular \ functional form for ", Cell[BoxData[ FormBox[ RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], TraditionalForm]]], ", but I shall use a Euclidean measure defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], "\[Congruent]", SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ StyleBox["x", FontWeight->"Bold"], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}], TraditionalForm]], "NumberedEquation"], Cell["in the following derivations.", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " Average distortion" }], "Subsection"], Cell[TextData[{ "The average distortion ", Cell[BoxData[ \(TraditionalForm\`D\)]], " may be obtained from the distortion measure ", Cell[BoxData[ FormBox[ RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], TraditionalForm]]], " and the input PDF ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], " as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{"D", "\[Congruent]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], RowBox[{"d", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}]}]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:3"], Cell[TextData[{ "This averaging process produces a global measure of the distortion which \ the encoding/decoding operation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}], TraditionalForm]]], " produces when applied to a set of input vectors characterised by the PDF \ ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]]], ". This global measure ", Cell[BoxData[ \(TraditionalForm\`D\)]], " is the Lyapunov function for vector quantiser design - it must be \ minimised." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Variation of distortion with encoding/decoding scheme" }], "Subsection"], Cell[TextData[{ "The encoding operation ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " and the decoding operation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " are chosen in such a way that the average distortion ", Cell[BoxData[ \(TraditionalForm\`D\)]], " is minimised. I need to compute the gradient of ", Cell[BoxData[ \(TraditionalForm\`D\)]], " with respect to variations of the functions ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " - this is achieved by using the machinery of functional differentiation \ (or, equivalently, variational calculus). Functionally differentiating ", Cell[BoxData[ \(TraditionalForm\`D\)]], " produces" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["D", FontSlant->"Italic"]}]], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ FractionBox["\[Delta]", RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["\[Xi]", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["y", FontWeight->"Bold"]}]], " ", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}], ")"}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["\[Xi]", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}]}]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ RowBox[{"-", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}], RowBox[{ StyleBox["\[Integral]", FontWeight->"Plain"], RowBox[{ StyleBox[ RowBox[{ StyleBox["d", FontWeight->"Plain"], StyleBox["y", FontWeight->"Bold"]}]], StyleBox[" ", FontWeight->"Plain"], FractionBox[ RowBox[{ StyleBox["\[PartialD]", FontWeight->"Plain"], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}], RowBox[{"\[PartialD]", StyleBox["y", FontWeight->"Bold"]}]], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ RowBox[{"+", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}]}], RowBox[{ StyleBox["\[Integral]", FontWeight->"Plain"], RowBox[{ StyleBox[ RowBox[{ StyleBox["d", FontWeight->"Plain"], StyleBox["y", FontWeight->"Bold"]}]], StyleBox[" ", FontWeight->"Plain"], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}], FractionBox[ StyleBox["\[PartialD]", FontWeight->"Plain"], RowBox[{"\[PartialD]", StyleBox["y", FontWeight->"Bold"]}]], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", SubscriptBox[ RowBox[{ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], StyleBox[" ", FontWeight->"Plain"], "[", RowBox[{ FractionBox[ StyleBox["\[PartialD]", FontWeight->"Plain"], RowBox[{"\[PartialD]", StyleBox["y", FontWeight->"Bold"]}]], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}], "]"}], RowBox[{ StyleBox["y", FontWeight->"Bold"], "=", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]]}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->{"Ed:Problem1", "Eq:4"}], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["D", FontSlant->"Italic"]}]], RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["x", FontWeight->"Bold"]}]], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]], "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ FractionBox["\[Delta]", RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["x", FontWeight->"Bold"]}]], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{"2", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}], RowBox[{"(", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], ")"}]}]}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->"Eq:5"], Cell[TextData[{ "In the first line of ", ButtonBox["equation", ButtonData:>"Eq:4", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:4"], ") I changed the dummy ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " integration variable to a ", Cell[BoxData[ FormBox[ StyleBox["\[Xi]", FontWeight->"Bold"], TraditionalForm]]], " to avoid a notation clash, and I used the identity ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox["\[Integral]", FontWeight->"Plain"], RowBox[{ StyleBox[ RowBox[{ StyleBox["d", FontWeight->"Plain"], StyleBox["y", FontWeight->"Bold"]}]], StyleBox[" ", FontWeight->"Plain"], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}], ")"}]}]}], "\[Congruent]", "1"}], TraditionalForm]]], " to simplify the ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}], TraditionalForm]]], " dependence of the integrand ready for functional differentiation. I \ derive the second line by using" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ RowBox[{"\[Delta]\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["\[Xi]", FontWeight->"Bold"], ")"}]}], ")"}], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", RowBox[{ RowBox[{"-", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], "-", StyleBox["\[Xi]", FontWeight->"Bold"]}], ")"}]}], FractionBox[ RowBox[{ StyleBox["\[PartialD]", FontWeight->"Plain"], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}], RowBox[{"\[PartialD]", StyleBox["y", FontWeight->"Bold"]}]]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "and then integrating out the ", Cell[BoxData[ FormBox[ StyleBox["\[Xi]", FontWeight->"Bold"], TraditionalForm]]], " variable. Note that the functional derivative has now become a partial \ derivative. I obtain the third line by integration by parts (surface terms \ are zero), and finally the fourth line by integrating out the ", Cell[BoxData[ FormBox[ StyleBox["y", FontWeight->"Bold"], TraditionalForm]]], " variable. ", ButtonBox["Equation", ButtonData:>"Eq:5", ButtonStyle->"Hyperlink"], " (5) is much simpler to derive, because it uses only the result" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["x", FontWeight->"Bold"]}]], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}], RowBox[{ SuperscriptBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["x", FontWeight->"Bold"]}]], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]], "=", RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}], TraditionalForm]], "NumberedEquation"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Optimising the encoding scheme" }], "Subsection"], Cell[TextData[{ "Firstly, I shall minimise ", Cell[BoxData[ \(TraditionalForm\`D\)]], " with respect to variations of ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ". Assuming that ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[NotEqual]", "0"}], TraditionalForm]]], " then ", Cell[BoxData[ FormBox[ RowBox[{ FractionBox[ StyleBox[ RowBox[{"\[Delta]", StyleBox["D", FontSlant->"Italic"]}]], RowBox[{ StyleBox[ RowBox[{"\[Delta]", StyleBox["y", FontWeight->"Bold"]}]], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], "=", "0"}], TraditionalForm]]], " in ", ButtonBox["equation", ButtonData:>"Eq:4", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:4"], ") implies" }], "Text", CellTags->"Ed:Change2"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", RowBox[{GridBox[{ {\(arg\ min\)}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", StyleBox["x", FontWeight->"Bold"]}], "\[RightBracketingBar]"}], "2"]}]}], TraditionalForm]], "NumberedEquation", CellTags->{"Ed:Change3", "Eq:8"}], Cell[TextData[{ "Thus the optimum function ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " is completely determined by the current ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " which is itself optimised by using ", ButtonBox["equation", ButtonData:>"Eq:5", ButtonStyle->"Hyperlink"], " (5). Inspection of ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") reveals that the optimum ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " is a nearest neighbour classffier which seeks that ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " (for all ", Cell[BoxData[ FormBox[ StyleBox["y", FontWeight->"Bold"], TraditionalForm]]], ") that is closest to ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Optimising the decoding scheme" }], "Subsection"], Cell[TextData[{ "Secondly, I shall minimise ", Cell[BoxData[ \(TraditionalForm\`D\)]], " with respect to variations of ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], ". ", ButtonBox["Equation", ButtonData:>"Eq:5", ButtonStyle->"Hyperlink"], " (5) leads immediately to" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "=", FractionBox[ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}], StyleBox["x", FontWeight->"Bold"]}]}], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], RowBox[{"\[Delta]", "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "-", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], ")"}]}]}]]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:9"], Cell[TextData[{ "This updates ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " to be the arithmetic mean of all the input vectors ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " that satisfy ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "=", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " Linde-Buzo-Gray (LBG) algorithm" }], "Subsection"], Cell[TextData[{ "Updating the decoding operation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " (see ", ButtonBox["equation", ButtonData:>"Eq:9", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:9"], ")) causes the nearest neighbour solution for the encoding operation ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " (see ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ")) to be disrupted. This dilemma can be resolved by alternately optimising \ the encoding then the decoding operations using the following algorithm \ (known as the LBG algorithm ", "[", ButtonBox["2", ButtonData:>"Ref:LindeBuzoGray1980", ButtonStyle->"Hyperlink"], "]", ")." }], "Text"], Cell[TextData[{ "\t1. Make an initial choice of decoding operation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], "." }], "Text", CellTags->"Step:1"], Cell[TextData[{ "\t2. Optirnise the encoding operation ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " using ", ButtonBox["equation", ButtonData:>"Eq:8", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:8"], ") to be a nearest neighour encoder for the current ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], "." }], "Text", CellTags->"Step:2"], Cell[TextData[{ "\t3. Encode the set of input data vectors (the training set), accumulating \ the arithmetic means in", " ", ButtonBox["equation", ButtonData:>"Eq:9", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:9"], ")", "." }], "Text"], Cell[TextData[{ "\t4. Optimise the decoding operation ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], " using", " ", ButtonBox["equation", ButtonData:>"Eq:9", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:9"], ")", "." }], "Text"], Cell[TextData[{ "\t5. If the previous step causes any significant change in ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], ", then go to ", ButtonBox["step 2", ButtonData:>"Step:2", ButtonStyle->"Hyperlink"], " and repeat the process." }], "Text"], Cell[TextData[{ "\t6. The algorithm has converged. Now consider the possibility that it is \ trapped in a local minimum of ", Cell[BoxData[ \(TraditionalForm\`D\)]], ". Repeat the whole process with various choices in ", ButtonBox["step 1", ButtonData:>"Step:1", ButtonStyle->"Hyperlink"], ", and choose the solution with the smallest value of ", Cell[BoxData[ \(TraditionalForm\`D\)]], "." }], "Text"], Cell[TextData[{ "The LBG algorithm is currently the most popular one for vector quantiser \ design. In my continuum language, the LBG algorithm finds a local minimum of \ the average distortion ", Cell[BoxData[ \(TraditionalForm\`D\)]], " by following a zigzag path in the product function space ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[CircleTimes]", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], "." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " Noisy-vector quantisation" }], "Section", CellTags->"Sect:3"], Cell[TextData[{ "In this section I shall present and discuss a simple derivation of an \ extension of the Linde-Buzo-Gray (LBG) vector quantisation method. See [", ButtonBox["1", ButtonData:>"Ref:EphraimGray1988", ButtonStyle->"Hyperlink"], "] for the original derivation of this method." }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Notation" }], "Subsection"], Cell["Some additional notation is now required.", "Text"], Cell[TextData[{ "\t", Cell[BoxData[ FormBox[GridBox[{ { SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], \(Idealised\ clean\ input\ vector\)}, { RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(Prior\ PDF\ describing\ distribution\ of\ clean\ \ input\ vectors\)}, { RowBox[{"P", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], "|", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], ")"}], RowBox[{ "PDF", " ", "describing", " ", "how", " ", "noisy", " ", "input", " ", "data", " ", StyleBox["x", FontWeight->"Bold"], Cell[TextData[StyleBox["", FontWeight->"Bold"]]], " ", "is", " ", "derived"}]}, { RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "|", StyleBox["x", FontWeight->"Bold"]}], ")"}], RowBox[{ "Posterior", " ", "PDF", " ", "which", " ", "inverts", " ", RowBox[{"P", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], "|", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], ")"}]}]}, { RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], \(Joint\ PDF\ of\ clean\ and\ noisy\ input\ vectors\)} }], TraditionalForm]]] }], "Text", GridBoxOptions->{ColumnAlignments->{Left}}] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Encoding and decoding noisy data" }], "Subsection"], Cell[TextData[{ "The sequence shown in ", ButtonBox["equation", ButtonData:>"Eq:1", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:1"], ") is now modified to become" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], OverscriptBox["\[LongRightArrow]", RowBox[{"P", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], "|", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], ")"}]], StyleBox["x", FontWeight->"Bold"], OverscriptBox["\[LongRightArrow]", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]], StyleBox["y", FontWeight->"Bold"], StyleBox[ OverscriptBox[ StyleBox["\[LongRightArrow]", FontWeight->"Plain"], RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}]], FontWeight->"Plain"], SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:10"], Cell[TextData[{ "There is now an additional stage in which the unobserved clean input \ vector is stochastically modified (using ", Cell[BoxData[ FormBox[ RowBox[{"P", "(", RowBox[{ StyleBox["x", FontWeight->"Bold"], "|", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], ")"}], TraditionalForm]]], ") to produce the observed input data vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ". The goal now is to encode the noisy version ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " of the input vector ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], ", and then to decode it to produce a reconstruction ", Cell[BoxData[ FormBox[ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], TraditionalForm]]], " of ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], "." }], "Text"], Cell[TextData[Cell[TextData[{ " ", ButtonBox["OPEN", ButtonData:>{ URL[ "http://www.luttrell.org.uk/papers/sp4_110/fig2.gif"], None}, Active->True, ButtonStyle->"Hyperlink"], " " }]]], "NumberedFigure", TextAlignment->Center, CellTags->"Fig:2"], Cell["Encoding and decoding noisy input data", "Caption"], Cell[TextData[{ "In ", ButtonBox["Figure", ButtonData:>"Fig:2", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:2"], " 1 represent the encoding and decoding process (of ", ButtonBox["equation", ButtonData:>"Eq:10", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:10"], ")) pictorially. Note that the decoding process bypasses the noisy input \ space (which ", ButtonBox["Figure", ButtonData:>"Fig:1", ButtonStyle->"Hyperlink"], " ", CounterBox["NumberedFigure", "Fig:1"], " is concerned with), and instead directly reconstructs the underlying \ clean input ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], "." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Modified distortion measure" }], "Subsection"], Cell[TextData[{ ButtonBox["Equation", ButtonData:>"Eq:10", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:10"], ") is a more subtle process than ", ButtonBox["equation", ButtonData:>"Eq:1", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:1"], "), because one cannot directly observe ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], " in order to calculate the reconstruction distortion - at best one can \ merely estimate the true distortion. As before, I shall use a Euclidean \ measure, which leads to a true distortion defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"d", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}], "\[Congruent]", SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:11"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Modified average distortion" }], "Subsection"], Cell[TextData[{ ButtonBox["Equation", ButtonData:>"Eq:3", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:3"], ") must now be replaced by" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"D", "\[Congruent]", "\[AlignmentMarker]", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ",", StyleBox["x", FontWeight->"Bold"]}], ")"}], RowBox[{"d", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "[", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "|", StyleBox["x", FontWeight->"Bold"]}], ")"}], RowBox[{"d", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ",", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], ")"}]}]}], "]"}]}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->"Eq:12"], Cell[TextData[{ "Comparing ", ButtonBox["equation", ButtonData:>"Eq:12", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:12"], ") with ", ButtonBox["equation", ButtonData:>"Eq:3", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:3"], "), the quantity in square brackets should be interpreted as a modified \ distortion measure defined entirely in terms of known quantities." }], "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Simplified result for Euclidean distortion" }], "Subsection"], Cell[TextData[{ "When the Euclidean distortion of ", ButtonBox["equation", ButtonData:>"Eq:11", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:11"], ") is inserted into ", ButtonBox["equation", ButtonData:>"Eq:12", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:12"], ") I obtain" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{"D", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], " ", "[", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "|", StyleBox["x", FontWeight->"Bold"]}], ")"}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}]}], "]"}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}]}], "+", "constant"}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, CellTags->"Eq:13"], Cell[TextData[{ "where the function ", Cell[BoxData[ FormBox[ RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " is defined as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[Congruent]", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], RowBox[{"P", "(", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "|", StyleBox["x", FontWeight->"Bold"]}], ")"}], SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:14"], Cell[TextData[{ "which is the conditional expected value of ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], " given ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "." }], "Text"], Cell[TextData[{ "When ", Cell[BoxData[ \(TraditionalForm\`D\)]], " is minimised with respect to variations of ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " to yield" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", RowBox[{GridBox[{ {\(arg\ min\)}, { StyleBox["y", FontWeight->"Bold"]} }], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], "-", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], "\[RightBracketingBar]"}], "2"]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Ed:Change4"], Cell[TextData[{ "one sees that ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " is a function only of ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], StyleBox["(", FontWeight->"Plain"], StyleBox["x", FontWeight->"Bold"], StyleBox[")", FontWeight->"Plain"]}], TraditionalForm]], FontWeight->"Bold"], ". Therefore, insofar as optimisation is concerned, I can simplify the \ expression for ", Cell[BoxData[ \(TraditionalForm\`D\)]], " in ", ButtonBox["equation", ButtonData:>"Eq:13", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:13"], ") as follows" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{"D", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}]}], "+", "constant"}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], " ", RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", RowBox[{ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], "-", RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], ")"}], ")"}]}], "\[RightBracketingBar]"}], "2"]}]}], "+", "constant"}]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, CellTags->"Eq:16"], Cell[TextData[{ "where I have used ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], ")"}]}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], "=", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], " ", RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}]}]}], TraditionalForm]]], "." }], "Text"], Cell[TextData[{ ButtonBox["Equation", ButtonData:>"Eq:16", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:16"], ") is precisely the Euclidean distortion which results from encoding and \ decoding the conditional expected value of ", Cell[BoxData[ FormBox[ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], TraditionalForm]]], " given ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ". It says that a Euclidean distortion, when modified by the effects of \ noisy data, can nevertheless be expressed as another Euclidean distortion, in \ which the noisy input vector ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " is replaced by the conditional expected value of the clean input vector \ ", Cell[BoxData[ FormBox[ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], TraditionalForm]]], " (up to an additive constant term). Although this result was derived only \ for some special cases in [", ButtonBox["1", ButtonData:>"Ref:EphraimGray1988", ButtonStyle->"Hyperlink"], "], I have succeeded in showing that it holds whenever the distortion \ measure is Euclidean." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " ", "Some useful approximations" }], "Section", CellTags->"Sect:4"], Cell["\<\ In this section I shall calculate expressions for the distortion obtained \ under different, but related, quantisation conditions. Specifically, I wish \ to compare the distortions that result from\ \>", "Text"], Cell["\t1. Naive application of the LBG algorithm to noisy data.", "Text"], Cell["\t2. Application of the extended algorithm to the same data.", "Text"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Notation" }], "Subsection"], Cell["Some additional notation is now required.", "Text"], Cell[TextData[{ "\t", Cell[BoxData[ FormBox[GridBox[{ {"N", \(Dimensionality\ of\ input\ space\)}, {"R", \(Number\ of\ quantisation\ cells\)}, { RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(Quantisation\ cell\ density\)} }], TraditionalForm]]] }], "Text", GridBoxOptions->{ColumnAlignments->{Left}}] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Quantisation cell density" }], "Subsection"], Cell[TextData[{ "The problem of calculating an exact closed form expression for the \ Euclidean distortion ", Cell[BoxData[ \(TraditionalForm\`D\)]], " associated with vector quantising and reconstructing ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " is complicated. Minimising ", Cell[BoxData[ \(TraditionalForm\`D\)]], " leads to a solution, ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], ", which effectively divides up ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "-space into a number of quantisation cells, each of which is associated \ with a particular value of ", Cell[BoxData[ FormBox[ StyleBox["y", FontWeight->"Bold"], TraditionalForm]]], ". The detailed shape and extent of the quantisation cells, together with \ the input PDF, determine the value of ", Cell[BoxData[ \(TraditionalForm\`D\)]], ". It is the detail required to specify a solution that makes the exact \ calculation of ", Cell[BoxData[ \(TraditionalForm\`D\)]], " so difficult." }], "Text"], Cell[TextData[{ "I can make a very useful approximation by ensemble averaging ", Cell[BoxData[ \(TraditionalForm\`D\)]], " over the set of equivalent solutions. The exact details of the shape of \ the quantisation cells associated with a particular solution is washed out in \ this ensemble average, leaving the ensemble average value of ", Cell[BoxData[ \(TraditionalForm\`D\)]], " to be determined by some average property of the quantisation cells. For \ the ensemble average it is convenient to define the quantisation cell density \ ", Cell[BoxData[ FormBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " as follows" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[Congruent]", \(Number\ of\ quantisation\ cells\ per\ unit\ \ volume\)}], TraditionalForm]], "NumberedEquation"], Cell["\<\ This reduces the complexity of a detailed quantisation cell solution to a \ density function, which can easily be manipulated using standard analytic \ techniques.\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Minimum distortion using quantisation cell density" }], "Subsection"], Cell[TextData[{ "The typical separation of a pair of quantisation cells is proportional to \ ", Cell[BoxData[ FormBox[ SuperscriptBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(-\(1\/N\)\)], TraditionalForm]]], ", where ", Cell[BoxData[ \(TraditionalForm\`N\)]], " is the input dimensionality. I can estimate the Euclidean distortion as" }], "Text", CellTags->"Ed:Change5"], Cell[BoxData[ FormBox[ RowBox[{"D", "\[TildeEqual]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], SuperscriptBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(-\(2\/N\)\)]}]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "up to a constant of proportionality. I shall minimise ", Cell[BoxData[ \(TraditionalForm\`D\)]], " together with a Lagrange multiplier term which constrains the total \ number of quantisation cells, ", Cell[BoxData[ FormBox[ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}], TraditionalForm]]], ", to be constant. Thus I shall define the cost function ", Cell[BoxData[ \(TraditionalForm\`D\^\[Prime]\)]], " as" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{\(D\^\[Prime]\), "\[Congruent]", RowBox[{"D", "+", RowBox[{"\[Lambda]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}]}]}]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "Functionally differentiating ", Cell[BoxData[ \(TraditionalForm\`D\^\[Prime]\)]], " with respect to ", Cell[BoxData[ FormBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], ", and equating the result to zero, yields" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[Proportional]", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}], TraditionalForm]], "NumberedEquation"], Cell[TextData[{ "The constrant of proportionality must be adjusted to obtain the correct \ total number of quantisation cells ", Cell[BoxData[ \(TraditionalForm\`R\)]], ", where" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{"R", "\[Congruent]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}]}]}]}], TraditionalForm]], "NumberedEquation"], Cell["whence, finally, I obtain", "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", RowBox[{"R", FractionBox[ SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}]}]]}]}], TraditionalForm]], "NumberedEquation", CellTags->"Eq:22"], Cell[TextData[{ "This quantisation cell density will approximately minimise ", Cell[BoxData[ \(TraditionalForm\`D\)]], " - the solution becomes exact in the limit ", Cell[BoxData[ \(TraditionalForm\`N\[LongRightArrow]\[Infinity]\)]], "." }], "Text"], Cell[TextData[{ "The actual distortion that is realised by this optimum ", Cell[BoxData[ FormBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " is calculated as follows" }], "Text"], Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"D", "\[TildeEqual]", "\[AlignmentMarker]", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], SuperscriptBox[ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(-\(2\/N\)\)]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ RowBox[{\(R\^\(-\(N\/2\)\)\), FractionBox[ RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(\(-\(2\/N\)\) N\/\(N + 2\)\)]}]}], SuperscriptBox[ RowBox[{"[", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}]}], "]"}], \(-\(2\/N\)\)]]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", SuperscriptBox[ RowBox[{\(R\^\(-\(N\/2\)\)\), "[", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}]}], "]"}], \(\(N + 2\)\/N\)]}]}], TraditionalForm]], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->"Eq:23"], Cell["This result depends only on the input PDF, as expected.", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Comparison of old and new quantisation schemes" }], "Subsection"], Cell[TextData[{ ButtonBox["Equation", ButtonData:>"Eq:23", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:23"], ") expresses the distortion that is obtained when one optimises a vector \ quantiser (", Cell[BoxData[ FormBox[ RowBox[{ StyleBox["y", FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox[ StyleBox["x", FontWeight->"Bold"], "\[Prime]"], "(", StyleBox["y", FontWeight->"Bold"], ")"}], TraditionalForm]]], ") for encoding and decoding ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], ". However, we have the following two problems:" }], "Text"], Cell[TextData[{ "\t1. Design a vector quantiser for encoding/decoding ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], " optimally, then evaluate the conditional expectation from the \ reconstruction using ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "=", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], "." }], "Text"], Cell[TextData[{ "\t2. Evaluate the conditional expectation using ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "=", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], ", then design a vector quantiser for encoding/decoding ", Cell[BoxData[ FormBox[ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], TraditionalForm]]], " optimally." }], "Text"], Cell["\<\ Both of these problems are closely related to what I have already discussed, \ so I can estimate the corresponding distortions by applying the quantisation \ cell density approach.\ \>", "Text"] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Old and new quantisation cell densities" }], "Subsection"], Cell[TextData[{ "From ", ButtonBox["equation", ButtonData:>"Eq:22", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:22"], ") the quantisation cell densities are, respectively" }], "Text"], Cell[BoxData[{ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", "\[AlignmentMarker]", RowBox[{"R", FractionBox[ SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}]}]]}]}], TraditionalForm], "\n", FormBox[ RowBox[{ RowBox[{\(\[Rho]\_0\), "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], "=", "\[AlignmentMarker]", RowBox[{"R", FractionBox[ SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)], RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)]}]}]]}]}], TraditionalForm]}], "NumberedEquation", TextAlignment->AlignmentMarker], Cell[TextData[{ "where the two spaces are related through the function ", Cell[BoxData[ FormBox[ RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "=", RowBox[{ StyleBox[ SubscriptBox["x", StyleBox["0", FontWeight->"Plain"]], FontWeight->"Bold"], "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], " in ", ButtonBox["equation", ButtonData:>"Eq:14", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:14"], ")." }], "Text"], Cell[TextData[{ "These two densities may easily be transformed into each other's space \ (i.e. ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", StyleBox["x", FontWeight->"Bold"], ")"}], "\[LongRightArrow]", RowBox[{"\[Rho]", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}]}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{ RowBox[{\(\[Rho]\_0\), "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], "\[LongRightArrow]", RowBox[{\(\[Rho]\_0\), "(", StyleBox["x", FontWeight->"Bold"], ")"}]}], TraditionalForm]]], ") by introducing appropriate Jacobian factors - a density transforms in \ exactly the same way as a PDF. Thus" }], "Text", CellTags->"Ed:Change17"], Cell[BoxData[{ FormBox[ RowBox[{ RowBox[{"\[Rho]", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], "=", "\[AlignmentMarker]", RowBox[{"R", FractionBox[ RowBox[{ SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(-\(2\/\(N + 2\)\)\)]}], RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(-\(2\/\(N + 2\)\)\)]}]}]]}]}], TraditionalForm], "\n", FormBox[ RowBox[{ RowBox[{\(\[Rho]\_0\), "(", StyleBox["x", FontWeight->"Bold"], ")"}], "=", "\[AlignmentMarker]", RowBox[{"R", FractionBox[ RowBox[{ SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(2\/\(N + 2\)\)]}], RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(2\/\(N + 2\)\)]}]}]]}]}], TraditionalForm]}], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Automatic] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " Old and new distortions - general case" }], "Subsection"], Cell[TextData[{ "The old (", Cell[BoxData[ \(TraditionalForm\`D\)]], ") and new (", Cell[BoxData[ \(TraditionalForm\`D\_0\)]], ") distortions are evaluated as Euclidean distortions in ", Cell[BoxData[ FormBox[ SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], TraditionalForm]]], "-space, using ", Cell[BoxData[ FormBox[ RowBox[{"\[Rho]", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ RowBox[{\(\[Rho]\_0\), "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], TraditionalForm]]], ", respectively. Thus" }], "Text"], Cell[BoxData[{ FormBox[ RowBox[{ RowBox[{"D", "\[TildeEqual]", "\[AlignmentMarker]", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], SuperscriptBox[ RowBox[{"\[Rho]", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(-\(2\/N\)\)]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", RowBox[{ SuperscriptBox[ RowBox[{\(R\^\(-\(2\/N\)\)\), "[", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(-\(2\/\(N + 2\)\)\)]}]}], "]"}], \(2\/N\)], "[", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(-\(4\/\(N(N + 2)\)\)\)]}]}], "]"}]}], TraditionalForm], "\n", FormBox[ RowBox[{ RowBox[{\(D\_0\), "\[TildeEqual]", "\[AlignmentMarker]", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], SuperscriptBox[ RowBox[{\(\[Rho]\_0\), "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(-\(2\/N\)\)]}]}]}], "\[IndentingNewLine]", "=", "\[AlignmentMarker]", SuperscriptBox[ RowBox[{\(R\^\(-\(2\/N\)\)\), "[", RowBox[{"\[Integral]", RowBox[{ SubscriptBox[ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], "0"], SuperscriptBox[ RowBox[{"P", "(", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"], ")"}], \(N\/\(N + 2\)\)]}]}], "]"}], \(\(N + 2\)\/N\)]}], TraditionalForm]}], "NumberedEquation", TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->"Eq:26"], Cell[TextData[{ "These two expressions may be transformed to become integrals in ", Cell[BoxData[ FormBox[ StyleBox["x", FontWeight->"Bold"], TraditionalForm]]], "-space, yielding" }], "Text"], Cell[BoxData[{ FormBox[ RowBox[{"D", "=", "\[AlignmentMarker]", RowBox[{ SuperscriptBox[ RowBox[{\(R\^\(-\(2\/N\)\)\), "[", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)]}]}], "]"}], \(2\/N\)], "[", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(2\/N\)]}]}], "]"}]}], TraditionalForm], "\n", FormBox[ RowBox[{\(D\_0\), "=", "\[AlignmentMarker]", SuperscriptBox[ RowBox[{\(R\^\(-\(2\/N\)\)\), "[", RowBox[{"\[Integral]", RowBox[{ StyleBox[ RowBox[{"d", StyleBox["x", FontWeight->"Bold"]}]], " ", SuperscriptBox[ RowBox[{"P", "(", StyleBox["x", FontWeight->"Bold"], ")"}], \(N\/\(N + 2\)\)], SuperscriptBox[ RowBox[{"\[LeftBracketingBar]", FractionBox[ RowBox[{"\[PartialD]", SubscriptBox[ StyleBox["x", FontWeight->"Bold"], "0"]}], RowBox[{"\[PartialD]", StyleBox["x", FontWeight->"Bold"]}]], "\[RightBracketingBar]"}], \(2\/\(N + 2\)\)]}]}], "]"}], \(\(N + 2\)\/N\)]}], TraditionalForm]}], "NumberedEquation",\ TextAlignment->AlignmentMarker, SpanMaxSize->Infinity, CellTags->"Eq:27"], Cell[TextData[{ "One may use whichever of ", ButtonBox["equation", ButtonData:>"Eq:26", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:26"], ") or ", ButtonBox["equation", ButtonData:>"Eq:27", ButtonStyle->"Hyperlink"], " (", CounterBox["NumberedEquation", "Eq:27"], ") is the most convenient to evaluate the old and new distortions." }], "Text"] }, Closed]] }, Closed]], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], " Quantising ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data" }], "Section", CellTags->"Sect:5"], Cell[TextData[{ "In this section I shall apply the noisy vector quantisation technique to \ the problem of encoding ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distributed data. A specific application of this would be the encoding of \ coherent radar data, where a cross section ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is coherently illuminated and the scattered radiation is imaged to \ produce a pixel intensity ", Cell[BoxData[ \(TraditionalForm\`I\)]], ". The various stages in the process are" }], "Text"], Cell[BoxData[ \(TraditionalForm\`cross\ section\ \ \[Sigma]\(\[LongRightArrow]\&illumination\)scattered\ \ field\(\[LongRightArrow]\&\(imaging\ system\)\)image\ I\)], "NumberedEquation",\ CellTags->"Ed:Change6"], Cell[TextData[{ "Such images have unavoidable multiplicative noise called speckle, which \ carries no useful information about the underlying cross section of \ interest", Cell[BoxData[ FormBox[ ButtonBox["FOOTNOTE", ButtonData:>"Footnote:1", Active->True, ButtonStyle->"Hyperlink"], TextForm]]], ". Vector quantisation must therefore address the problem of encoding with \ a view to ultimately reconstructing ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " rather than ", Cell[BoxData[ \(TraditionalForm\`I\)]], "." }], "Text"], Cell[CellGroupData[{ Cell[TextData[{ CounterBox["Section"], ".", CounterBox["Subsection"], " ", "Compound distribution using hidden and visible variables" }], "Subsection"], Cell[TextData[{ "I now summarise a simple derivation of the ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Plain"], TraditionalForm]]], "-distribution that can be found in [", ButtonBox["4", ButtonData:>"Ref:Ward1980", ButtonStyle->"Hyperlink"], ", ", ButtonBox["5", ButtonData:>"Ref:Ward1981", ButtonStyle->"Hyperlink"], "]. The cross section ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is a set of hidden variables, and the image ", Cell[BoxData[ \(TraditionalForm\`I\)]], " is a set of visible variables. In the simplest uncorrelated ", Cell[BoxData[ FormBox[ StyleBox["K", FontSlant->"Italic"], TraditionalForm]]], "-distribution model I need consider only a single cross section and \ intensity variable, which have the following properties:" }], "Text"], Cell[TextData[{ "\t1. ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " obeys Gamma statistics" }], "Text"], Cell[BoxData[ \(TraditionalForm\`P(\[Sigma] | \[Sigma]\_0, \[Nu]) = \(1\/\(\ \[CapitalGamma](\[Nu])\)\) \(\[Sigma]\^\(\[Nu] - 1\)\/\[Sigma]\_0\%\[Nu]\) e\^\(-\(\[Sigma]\/\[Sigma]\_0\)\)\)], "NumberedEquation", CellTags->{"Ed:Change8", "Eq:29"}], Cell[TextData[{ "where ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\_0\)]], " is a scale parameter, and ", Cell[BoxData[ \(TraditionalForm\`\[Nu]\)]], " is an order parameter. The average cross section ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\[Sigma]\[RightAngleBracket]\)]], " of ", Cell[BoxData[ \(TraditionalForm\`\[Sigma]\)]], " is then given by ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\[Sigma]\[RightAngleBracket] = \(\ \[Sigma]\_0\) \[Nu]\)]], ". When ", Cell[BoxData[ \(TraditionalForm\`\[Nu]\[LongRightArrow]\[Infinity]\)]], " (whilst holding ", Cell[BoxData[ \(TraditionalForm\`\[LeftAngleBracket]\[Sigma]\[RightAngleBracket]\)]], " constant) this PDF tends to the Dirac delta function ", Cell[BoxData[ \(Tr